串基本操作：求子串、比较操作、模式匹配：暴力遍历、KMP算法；及next、nextval数组求法

#include<iostream> #define MAXSIZE 255 //舍弃ch[0]，使位序=数组下标。使用变量length表示长度。 //定义串：使用静态数组方法。 typedef struct { char ch[MAXSIZE];//预定义最大串长尾255 int length; }SString; //求子串：用Sub返回串S的第pos个字符起长度为len的子串 bool SubString(SString &Sub,SString S,int pos,int len) { //判断子串范围是否合法 if(pos+len-1>S.length)return false; for(int i=pos;i<pos+len;i++) { Sub.ch[i-pos+1]=S.ch[i]; } Sub.length=len; return true; } //比较操作：若S>T，返回值>0；S=T，返回值=0；S<T，返回值<0 int StrCompare(SString S,SString T) { for(int i=1;i<S.length&&i<T.length;i++) { if(S.ch[i]!=T.ch[i])return S.ch[i]-T.ch[i]; } //扫描过的所有字符相同，则长度大的串更大 return S.length-T.length; } //模式匹配算法1：运用其他函数 //定位字串：定位操作，若主串S中存在与串T值相同的子串，则返回它在子串中第一次出现的位置；否则函数值为0 //使用前面的取子串方法，依此取子串与T比较 int Index1(SString S,SString T) { int i=1,n=S.length,m=T.length; SString Sub;//用于暂存子串 while(i<=n-m+1) { SubString(Sub,S,i,m); if(StrCompare(Sub,T)!=0)i++; else { return i;//返回字串在主串中的位置 } } return 0;//主串中不存在与T相等的子串 } //模式匹配算法2：暴力遍历 //若模式串长度为m，主串长度为n //匹配成功的最好时间复杂度：O(m)；匹配失败的最好时间复杂度：O(n-m+1)≈O(n)(n>>m，i不回退) //最坏时间：O((n-m+1)*m)=O(nm) int Index2(SString S,SString T) { int k=1; int i=k,j=1; while (i<=S.length-T.length+1&&j<=T.length) { if(S.ch[i]==T.ch[i]) { i++; j++; } else { k++; i=k; j=1; } } if(j>T.length)return k; else return 0; } //模式匹配算法3：KMP算法 //求next数组 void get_next(SString T,int next[]) { int i=1,j=0; next[1]=0; while(i<T.length) { if(j==0||T.ch[i]==T.ch[j]) { i++; j++; next[i]=j; } else { j=next[j]; } } } //优化next数组；因为next数组还是有一些冗余的比较，优化后得到nextval数组 void get_nextval(SString T,int nextval[]) { int i=1,j=0; nextval[1]=0; while (i<T.length) { if(j==0||T.ch[j]==T.ch[i]) { i++; j++; if(T.ch[i]!=T.ch[j])nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } } //KMP算法：平均时间复杂度O(n+m) int index_KMP(SString S,SString T) { int i=1,j=1; int next[T.length+1]; get_next(T,next); //get_nextval(T,next); while (i<=S.length&&j<=T.length) { if(j==0||S.ch[i]==T.ch[j]) { i++; j++; } else { j=next[j]; } } if(j>T.length)return i-T.length; else return 0; }