Find-Common-Subsequences/FindCommonSubsequences.java at main · fe-jackson/Find-Common-Subsequences · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
//Fe Jackson
//Program 3

import java.util.*;

public class FindCommonSubsequences {
	private ArrayList<String> string_list;
	private LinkedList<String> common_substring_list;

	public FindCommonSubsequences (Collection<? extends CharSequence> to_search) {
		string_list = new ArrayList<String>();
		Iterator<? extends CharSequence> it = to_search.iterator ();

		while (it.hasNext ())
			string_list.add(it.next().toString());

		common_substring_list = new LinkedList <String> ();
		makeList();
	}

	public ArrayList<String> getCommonSubsequences () {
		ArrayList<String> get = new ArrayList<String>(common_substring_list);
		return get;
	}

	private void makeList () {
		int length = string_list.size ();

		if (length ==  1) {
			if (string_list.get (0).length () >= 5)
				common_substring_list.add (string_list.get (0));
		}
		else if (length > 1) {
			String first_string = string_list.get (0);
			String cur_string = string_list.get (1);
			int cur_index = 1;
			boolean no_common_substrings = false;

			if (first_string.length () < 5 || cur_string.length() < 5)
				no_common_substrings = true;
			else {
				if (compareTwo (first_string, cur_string) == true){
					checkWholeList (); //check the rest of the list for matches
					optimizeList ();
				}
			}
		}
	}

	private boolean compareTwo (String str1, String str2) {
		int first_index = 0;
		int last_index = 5;
		int temp;
		int str1_length = str1.length ();
		boolean substring_found = false;

		while (last_index <= str1_length) {
			if (substring_found = str2.contains (str1.substring (first_index, last_index))) {
				common_substring_list.add (str1.substring (first_index, last_index));
				temp = last_index + 1;

				while (substring_found == true && temp < str1_length) {
					if (substring_found = str2.contains (str1.substring (first_index, temp)))
						common_substring_list.add (str1.substring (first_index, temp));

					++temp;
				}
			}
			++first_index;
			++last_index;
		}

		if (common_substring_list.isEmpty() == false)
			substring_found = true;

		return substring_found;
	}

	private void checkWholeList () {
		int length = string_list.size (); //the length (size) of string_list
		int cur_index1; //the current index in string_list
		int cur_index2; //the current index in common_substring_list
		String cur_string;

		for(cur_index1 = 2; cur_index1 < length && common_substring_list.isEmpty () == false; ++cur_index1) {
			cur_string = string_list.get(cur_index1);
			cur_index2 = 0;

			while (cur_index2 < common_substring_list.size ()) {
				if (cur_string.contains (common_substring_list.get(cur_index2)))
					++cur_index2;
				else
					common_substring_list.remove (cur_index2);
			}
			++cur_index1;
		}
	}

	private void optimizeList () {
		int index1 = 0;
		int index2;
		String cur;
		LinkedList <String> temp = new LinkedList<String>();
		int biggest;
		int length;

		while (index1 < common_substring_list.size ()) {
			if (common_substring_list.get(index1).length() > 15)
				common_substring_list.remove(index1);
			else
				++index1;
		}

		for (index1 = 0; index1 < common_substring_list.size (); ++index1) {
			cur = common_substring_list.get (index1);
			index2 = index1 + 1;

			while (index2 < common_substring_list.size ()) {
				if (index2 != index1 && cur.contains (common_substring_list.get(index2))) {
					common_substring_list.remove(index2);

					if (index1 > index2)
						--index1;
				}
				else if (index2 != index1 && common_substring_list.get(index2).contains (cur)) {
					common_substring_list.remove (index1);
					index2 = common_substring_list.size ();
					--index1;
				}
				else
					++index2;
			}
		}
		while (common_substring_list.isEmpty () == false) {
			length = common_substring_list.size ();
			cur = common_substring_list.get(0);
			biggest = 0;

			for (index1 = 1; index1 < length; ++index1) {
				if (common_substring_list.get(index1).length() > cur.length()) {
					biggest = index1;
					cur = common_substring_list.get(index1);
				}
			}
			temp.add (cur);
			common_substring_list.remove(biggest);
		}
		common_substring_list.addAll (temp);
	}
}