6. 数据结构—串的匹配算法
1.简单匹配算法(暴力算法)
//模式匹配(暴力算法)
int Index(SString S,SString T){int i=1,j=1;while(i<=S.length&&j<=T.length){if(S[i]==T[i]){i++;j++;}else{i=i-j+2; //最开始匹配的位置的后一个j=1; //从头匹配 }}if(j>T.length)return i-T.length;return return 0;
}时间复杂度分析：
假设主串长度为n,待匹配的串长度为m,则最坏时间复杂度为O(nm)。
主串最多需要匹配n-m+1次，每次最多匹配m次(匹配到最后一个发现不匹配了)，
所以也就是(n-m+1)*m=nm-m^2+m,因为一般都是n>>m，所以后面的-m^2+m可以省略，也就是O(nm)的时间复杂度。