You can use LCS(Longest Common Subsequence) see these: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
public class LCS {
public static void main(String[] args) {
String x = StdIn.readString();
String y = StdIn.readString();
int M = x.length();
int N = y.length();
// opt[i][j] = length of LCS of x[i..M] and y[j..N]
int[][] opt = new int[M+1][N+1];
// compute length of LCS and all subproblems via dynamic programming
for (int i = M-1; i >= 0; i--) {
for (int j = N-1; j >= 0; j--) {
if (x.charAt(i) == y.charAt(j))
opt[i][j] = opt[i+1][j+1] + 1;
else
opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
}
}
// recover LCS itself and print it to standard output
int i = 0, j = 0;
while(i < M && j < N) {
if (x.charAt(i) == y.charAt(j)) {
System.out.print(x.charAt(i));
i++;
j++;
}
else if (opt[i+1][j] >= opt[i][j+1]) i++;
else j++;
}
System.out.println();
}
}
Other solution is Aho–Corasick string matching algorithm see this : Fast algorithm for searching for substrings in a string