看小甲鱼的kmp看了一晚上明白了不少但优化那里还是不太清楚

小海儿~

看小甲鱼的kmp看了一晚上明白了不少但优化

1. #include<iostream>
   
2. #include<cstring>
   
3. using namespace std;
   
4. int get_next(string t,int next[])
   
5. {
   
6.         int i=1;
   
7.         int j=0;
   
8.         next[1]=0;
   
9.        
   
10.         while(i<t[0])
    
11.         {
    
12.                 if(j==0 || t[i]==t[j])
    
13.                 {
    
14.                         i++;
    
15.                         j++;
    
16.                         //next[i]=j;       
    
17.                         if(t[i]!=t[j])
    
18.                         {
    
19.                                 next[i]=j;
    
20.                         }       
    
21.                         else
    
22.                         {
    
23.                                 next[i]=next[j];
    
24.                         }
    
25.                 }
    
26.                 else
    
27.                 {
    
28.                         j=next[j];
    
29.                 }
    
30.         }
    
31. }
    
32. 
    
33. int index_kmp(string s,string t,int pos)
    
34. {
    
35.         int i=pos;
    
36.         int j=1;
    
37.         int next[255];       
    
38.         get_next(t,next);
    
39.        
    
40.         while(i<=s[0]&&j<=t[0])
    
41.         {
    
42.                 if(0==j || s[i]==t[j])
    
43.                 {
    
44.                         i++;
    
45.                         j++;
    
46.                 }
    
47.                 else
    
48.                 {
    
49.                         j=next[j];
    
50.                 }
    
51.         }
    
52.        
    
53.         if(j>t[0])
    
54.                 return i-t[0];
    
55.         else
    
56.                 return 0;
    
57. }
    
58. 
    
59. int main()
    
60. {
    
61.         char s[255]=" sddsfdsfsfsfefe";
    
62.         char t[25]=" fds";
    
63.        
    
64.         s[0]=strlen(s)-1;
    
65.         t[0]=strlen(t)-1;
    
66.        
    
67.         cout<<index_kmp(s,t,1);
    
68.         return 0;       
    
69. }
    

复制代码

那里还是不太清楚 不能不把代码粘上来