学步园

/*动态顺序串*/<br /> #include <iostream><br /> using namespace std;<br /> /*动态顺序串的定义*/<br /> typedef struct DString<br /> {<br /> char *ch;<br /> int length;<br /> }DString;<br /> /*初始化动态串*/<br /> void initString(DString &S)<br /> {<br /> S.ch=new char[100];<br /> S.length=0;<br /> }<br /> /*串常量的长度*/<br /> int lenString(char chars[])<br /> {<br /> int len=0;<br /> int i=0;<br /> while(chars[i]!='/0')<br /> {<br /> len++;<br /> i++;<br /> }<br /> return len;<br /> }</p> <p>/*串赋值*/<br /> void strEval_Sq(DString &S,char chars[])<br /> {<br /> int lenStr;<br /> if(S.ch)<br /> delete S.ch;//若串已存在，则释放s的空间。<br /> lenStr=lenString(chars);<br /> if(lenStr==0)<br /> {<br /> S.ch=NULL;<br /> S.length=0;<br /> }<br /> else<br /> {<br /> S.ch=new char[lenStr];<br /> int i=0;<br /> while(chars[i]!='/0')<br /> {<br /> S.ch[i]=chars[i];<br /> i++;<br /> }<br /> S.length=lenStr;<br /> }<br /> }<br /> /*销毁串*/<br /> void destroyStr(DString &S)<br /> {<br /> delete S.ch;<br /> S.length=0;<br /> }</p> <p>/*串连接*/<br /> void concatStr(DString &S,DString T)//将串T连接到串S的后面，需要一个临时数组。<br /> {<br /> DString temp;<br /> if(T.length!=0)<br /> {<br /> temp.ch=new char[S.length+T.length];//构造一个临时的串<br /> int i=0,j=0;<br /> for(i;i<S.length;i++,j++)<br /> temp.ch[j]=S.ch[i];//将串S复制到temp中<br /> i=0;<br /> for(i;i<T.length;i++,j++)<br /> temp.ch[j]=T.ch[i];//将串T复制到temp中<br /> S.ch=temp.ch;<br /> S.length=S.length+T.length;<br /> delete []temp.ch;<br /> }<br /> }<br /> /*求从某个位置开始，特定长度的子串*/<br /> void strSub_Sq(DString &Sub,DString S,int i,int len)<br /> {<br /> if(i<1||i>S.length||len<0||len>S.length-i+1)<br /> cout<<"Parameters Error!";<br /> if(Sub.ch)<br /> delete Sub.ch;//若串已存在，释放其空间<br /> if(len==0)<br /> {<br /> Sub.ch=NULL;<br /> Sub.length=0;<br /> }//以上三个if是考虑特殊情况。<br /> else<br /> {<br /> Sub.ch=new char[len];<br /> for(int j=0;j<len;j++)<br /> Sub.ch[j]=S.ch[i-1+j];<br /> Sub.length=len;<br /> }<br /> }<br /> /*串比较*/<br /> int cmpStr_Sq(DString S,DString T)<br /> {<br /> for(int i=0;(i<S.length)&&(i<T.length);i++)<br /> if(S.ch[i]!=T.ch[i])<br /> return (S.ch[i]-T.ch[i]);//字符不同的情况。<br /> return (S.length-T.length);//字符相同，但长度不同的情况。<br /> }</p> <p>/*取主串中和模式串匹配的子串的首地址*/<br /> //简单的模式串匹配，BF<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span><br /> int strIndex_BF(DString &S,DString &T)<br /> {<br /> int i=1;<br /> int j=1;<br /> while(i<=S.length-T.length+1 && j<=T.length)<br /> {<br /> if(S.ch[i]==T.ch[j] || j==0)<br /> {<br /> i++;<br /> j++;<br /> }<br /> else<br /> {<br /> i=i-j+2;//i回溯到这次比较的起始位置的下一个位置。<br /> j=1;//j回溯到起始位置。<br /> }<br /> }<br /> if(j>T.length)<br /> return (i-j+1);<br /> else<br /> return 0;<br /> }</p> <p>//next的第一种算法<br /> int* getNext_1(DString T)<br /> {<br /> int *next=new int[T.length];<br /> int j=1;<br /> int k=0;<br /> next[j]=0;//设置初始值。<br /> while(j<T.length)<br /> {<br /> if(k==0||T.ch[j]==T.ch[k])<br /> {<br /> j++;<br /> k++;<br /> next[j]=k;<br /> }<br /> else<br /> k=next[k];<br /> }<br /> return next;<br /> }<br /> //next的第二种算法<br /> int* getNext_2(DString T)//将模式串也看成两个相同的主串和模式串来求next[]<br /> {<br /> int *next=new int[T.length];<br /> int j=1;//j表示的是数组next的下标<br /> int k=0;//k为next[j]的值<br /> next[j]=k;//设置初始值。<br /> while(j<T.length)<br /> {<br /> if(k==0||T.ch[j]==T.ch[k])//若k==0，即next[j]==k==0，则不论T.ch[j]和T.ch[k]是否相等都要向后移一位<br /> {<br /> j++;<br /> k++;<br /> if(T.ch[j]!=T.ch[k])//如果T.ch[j]和T.ch[k]相等，则T.ch[k]也会和主串中的字符不匹配，那就不需要做这一次比较了<br /> next[j]=k;<br /> else<br /> next[j]=next[k];//直接让next[j]等于next[k]就可以了<br /> }<br /> else<br /> k=next[k];//如果不相等的话，那么让k指针回溯，一直回溯到下一个相等的地方。<br /> }<br /> return next;<br /> }</p> <p>//改进的模式串匹配，KMP算法<br /> int strIndex_KMP(DString &S,DString &T)<br /> {<br /> int* next=getNext_2(T);<br /> int i=1;<br /> int j=1;<br /> while(i<=S.length-T.length+1 && j<=T.length)<br /> {<br /> if(j==0 || S.ch[i]==T.ch[j])<br /> {<br /> i++;<br /> j++;<br /> }<br /> else<br /> j=next[j];<br /> }<br /> if(j>T.length)<br /> return i-j+1;<br /> else<br /> return 0;<br /> }<br /> /*创建动态顺序串*/<br /> void creatString(DString &S,int n)<br /> {<br /> int i;</p> <p> for(i=1;i<=n;i++)<br /> {<br /> cin>>S.ch[i];<br /> S.length++;<br /> }<br /> }<br /> /*输出动态串*/<br /> void outputString(DString &S)<br /> {<br /> int i;<br /> for(i=1;i<=S.length;i++)<br /> {<br /> cout<<S.ch[i];<br /> }<br /> cout<<endl;<br /> }</p> <p>void main()<br /> {<br /> freopen("in.txt","r",stdin);<br /> DString T;<br /> DString S;<br /> initString(S);<br /> initString(T);<br /> creatString(S,26);<br /> creatString(T,3);</p> <p> //creatString(T,12);</p> <p> //concatStr(S,T);<br /> //<br /> outputString(S);<br /> outputString(T);<br /> cout<<strIndex_BF(S,T)<<endl;<br /> cout<<strIndex_KMP(S,T)<<endl;</p> <p>}