子序列：可以连续也可以不连续
子数组，子串：一定连续
int getIndexof(str1,str2) 用的就是KMP ， O(N) ，c++、java的实际时间复杂度要更好
1、一个字符的信息：前面字符的最长前缀与最长后缀的匹配长度
2、0位置-1,1位置0，…
public static int getIndexOf(char[] str1,char[] str2){ if(str1.length<str2.length || str2.length<1){ return -1; } int i1=0,i2=0; int[] next = getNextArray(str2); while(i1<str1.length && i2<str2.length){ if(str1[i1]==str2[i2]){ i1++; i2++; }else if(next[i2]==-1){ i1++; }else{ i2=next[i2]; } } return i2==str2.length? i1-i2 : -1; } public static int[] getNextArray(char[] str2){ if(str2.length == 1){ return new int[]{-1}; } int[] next = new int[str2.length]; next[0] = -1; next[1] = 0; int i=2; int cn=0; while(i<str2.length){ if(str[i-1] == str2[cn]){ next[i++] = ++cn; }else if(next[cn]>0){ cn = next[cn]; }else{ next[i++] = 0; } } return next; }求原始串添加成为最短的两个原始串
求两树包含问题
怎么确定一个字符串是由另一个字符串重复多次得到的
