hdu poj KMP简单题目总结

hdu 3336

 题意：输入一个字符串求每个前缀在串中出现的次数和

sol:只要稍微理解下next 数组的含义就知道只要把每个有意义的next值得个数加起来即可

PS：网上有dp解法orz，dp[i]表示以i为前缀串结尾的前缀串的总和，方程很容易写出

// 字符串上KMP(水)
// 从前向后扫，失配函数的位置就是一个前缀的位置减1
// 加起来就好了
//  by acvc
#include<cstring>
#include<cstdio>
#include<algorithm>
using  namespace std;
const  int MAX =  200000;
const  int MOD =  10007;
char str[MAX];
int next[MAX],vis[MAX];
int main()
{
     int cas,n;
    scanf( " %d ",&cas);
     while(cas--)
    {
        scanf( " %d %s ",&n,str);
        next[ 0]=next[ 1]= 0;
         for( int i= 1;i<n;i++)
        {
             int j=next[i];
             while(j&&str[i]!=str[j]) j=next[j];
             if(str[i]==str[j])
            next[i+ 1]=j+ 1;
             else next[i+ 1]= 0;
        }
         int ans= 0,cnt= 0;
         for( int i= 0;i<n;i++)
        {
             if(next[i])
            {
             //     cnt++;
                ans=(ans+ 2)%MOD;
            }
             else
            ans=(ans+ 1)%MOD;
        }
         if(next[n]) ans=(ans+ 1)%MOD;
        printf( " %d\n ",(ans)%MOD);
    }
     return  0;

} 

 hdu 1358

题意：给出一个字符串求出每个前缀的最小周期

sol:next数组理解题目稍微想想就知道t=(len-next[len])

// kmp小深入题目
#include<cstdio>
#include<cstring>
#include<algorithm>
using  namespace std;
const  int MAX =  10000000+ 10;
char str[MAX];  int next[MAX];  // 失配函数
int main()
{
     int n,cnt= 0;
     while(scanf( " %d ",&n)> 0)
    {
        scanf( " %s ",str);
        next[ 0]=next[ 1]= 0;
         for( int i= 1;i<n;i++)
        {
             int j=next[i];
             while(j&&str[i]!=str[j]) j=next[j];
             if(str[i]==str[j]) next[i]=j+ 1;
             else next[i]= 0;
        }
        printf( " Test case #%d\n ",++cnt);
         for( int i= 2;i<=n;i++)
        {
             if(next[i]&&i%(i-next[i])== 0)
            printf( " %d %d\n ",i,i%(i-next[i]));
        }
    }
     return  0;

} 

 hdu1711

题意：给出两个数组，求出b在a中最先匹配的位置

sol：KMP裸题

 1  // 裸题
 2  #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5  using  namespace std;
 6  const  int MAX = 1e6+ 10;
 7  int next[MAX];
 8  int a[MAX],b[MAX];
 9  int main()
10 {
11      int cas,n,m;
12     scanf( " %d ",&cas);
13      while(cas--)
14     {
15         scanf( " %d %d ",&n,&m);
16          for( int i= 0;i<n;i++) scanf( " %d ",&a[i]);
17          for( int j= 0;j<m;j++) scanf( " %d ",&b[j]);
18         next[ 1]=next[ 0]= 0;
19          for( int i= 1;i<m;i++)
20         {
21              int j=next[i];
22              while(j&&b[i]!=b[j]) j=next[j];
23              if(b[i]==b[j]) next[i+ 1]=j+ 1;
24              else next[i+ 1]= 0;
25         }
26          int cur= 0,flag= 0;
27          for( int i= 0;i<n;i++)
28         {
29              while(cur&&a[i]!=b[cur]) cur=next[cur];
30              if(a[i]==b[cur]) cur++;
31              if(cur==m)
32             {
33                 flag= 1;
34                 printf( " %d\n ",i-cur+ 2);
35                  break;
36             }
37         }
38          if(!flag) printf( " -1\n ");
39     }
40      return  0;

41 }

 

hdu2087

题意：给定串1和串2求串2在串1中出现的顺序

sol；裸KMP从前向后扫一遍kmp就好了

 1 #include<cstring>
 2 #include<algorithm>
 3 #include<cstdio>
 4  using  namespace std;
 5  const  int MAX =  1000+ 10;
 6  char str1[MAX],str2[MAX];
 7  int next[MAX];
 8  int main()
 9 {
10      while(scanf( " %s ",str1)&&strcmp(str1, " # "))
11     {
12          int ans= 0;
13         scanf( " %s ",str2);
14          int n=strlen(str2); next[ 0]=next[ 1]= 0;
15          for( int i= 1;i<n;i++)
16         {
17              int j=next[i];
18              while(j&&str2[i]!=str2[j]) j=next[j];
19              if(str2[i]==str2[j]) next[i+ 1]=j+ 1;
20              else next[i+ 1]= 0;
21         }
22          int len=strlen(str1);  int j= 0;
23          for( int i= 0;i<len;i++)
24         {
25              while(j&&str1[i]!=str2[j]) j=next[j];
26              if(str1[i]==str2[j]) j++;
27              if(j==n)
28             {
29                 ans++;
30                 j= 0;
31             }
32         }
33         printf( " %d\n ",ans);
34     }
35      return  0;

36 }

 

 poj2406

题意：给定一个串求出串的最小周期

los:失配函数裸题啊

 1  // kmp-shui
 2  #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5  using  namespace std;
 6  const  int MAX = 1e6+ 10;
 7  char str[MAX];  int next[MAX];
 8  int main()
 9 {
10      int ans;
11      while( 1)
12     {
13         gets(str);  if(!strcmp(str, " . "))  break;
14          int n=strlen(str); next[ 0]=next[ 1]= 0;
15          for( int i= 1;i<n;i++)
16         {
17              int j=next[i];
18              while(j&&str[i]!=str[j]) j=next[j];
19              if(str[i]==str[j]) next[i+ 1]=j+ 1;
20              else next[i+ 1]= 0;
21         }
22          if(n%(n-next[n])== 0)
23         printf( " %d\n ",n/(n-next[n]));
24          else printf( " 1\n ");
25     }
26      return  0;

27 }

 

poj 2752

题意：给定一个串求出满足既是前缀又是后缀的串的起始位置

sol：又是一发next数组加深题目，很明显next数组指向的是最长的一个前缀串，所以最后一个指针指向的next就是一个最长前缀

之后从这个最长前缀末尾开始下一个指针又是前缀的最长前缀，而后缀和前缀相同，所以这个是第二长的前缀，只要递归结束即可

  1 //kmp题目shui by acvc

 
   2  
   
  // 
  kmp每次都是求的最长的前缀 
  
 
   3  
  #include<cstring> 
  
 4 #include<algorithm> 
  
 5 #include<cstdio> 
  
 6 #include<vector> 
  
 7  
  using  
  namespace std; 
  
 8  
  const  
  int MAX =  
  400000+ 
  10; 
  
 9  
  int next[MAX]; 
  
10  
  char str[MAX]; 
  
11 vector< 
  int> s; 
  
12  
  int main() 
  
13 { 
  
14      
  while(scanf( 
  " 
  %s 
  ",str)!=EOF) 
  
15     { 
  
16         s.clear(); 
  
17          
  int n=strlen(str); next[ 
  0]= 
  0,next[ 
  1]= 
  0; 
  
18          
  for( 
  int i= 
  1;i<n;i++) 
  
19         { 
  
20              
  int j=next[i]; 
  
21              
  while(j&&str[i]!=str[j]) j=next[j]; 
  
22              
  if(str[i]==str[j]) next[i+ 
  1]=j+ 
  1; 
  
23              
  else next[i+ 
  1]= 
  0; 
  
24         } 
  
25          
  // 
  for(int i=0;i<=n;i++) printf("%d ",next[i]);
 
  26  
       
  // 
      printf("\n"); 
  
 
  27  
           
  int j=strlen(str); 
  
28          
  while(j) 
  
29         { 
  
30             s.push_back(j); 
  
31             j=next[j]; 
  
32         } 
  
33          
  for( 
  int i=s.size()- 
  1;i>= 
  0;i--) 
  
34         { 
  
35              
  if(i==s.size()- 
  1) printf( 
  " 
  %d 
  ",s[i]); 
  
36              
  else printf( 
  " 
   %d 
  ",s[i]); 
  
37         } 
  
38         printf( 
  " 
  \n 
  "); 
  
39     } 
  
40      
  return  
  0; 
  
41 } 
 

 

 poj 2185

题意：输入一个矩阵由字符组成，求出矩阵的最小组成单位。

sol:网上好多代码都是错的，第一次学被误解了，今天重新修改这道题，其实找出每一行的周期串记录下个数,最后等于行数的肯定就是最小的宽。

求高直接公式就好了，

 
   1  
  /* 
  ***********************
 
   2  
  *    zhuyuqi            *
 
   3  
  *    QQ:1113865149      *
 
   4  
  *    [e-mail]  *
 
   5  
  ************************ 
  */ 
  
 6 #include <cstdio> 
  
 7 #include <cstring> 
  
 8 #include <algorithm> 
  
 9 #include <cmath> 
  
10 #include <vector> 
  
11 #include <list> 
  
12 #include <queue> 
  
13  
  using  
  namespace std; 
  
14  
  const  
  int MAX = 1e4+ 
  10; 
  
15  
  const  
  int inf =  
  0x3f3f3f3f; 
  
16  
  char str[MAX][ 
  80]; 
  
17  
  int next[MAX],ML[MAX],vis[MAX]; 
  
18  
  int main() 
  
19 { 
  
20  
  
21      
  int n,m;  
  int L,R; 
  
22      
  while(scanf( 
  " 
  %d %d 
  ",&n,&m)== 
  2) { 
  
23          
  for( 
  int i= 
  1;i<=n;i++) { 
  
24             scanf( 
  " 
  %s 
  ",str[i]+ 
  1); 
  
25         } 
  
26         
  // 
   for(int i=1;i<=n;i++) printf("%s\n",str[i]+1); 
  
 
  27  
          memset(ML, 
  0, 
  sizeof(ML)); 
  
28          
  if(m> 
  1) { 
  
29              
  for( 
  int i= 
  1;i<=n;i++) { 
  
30                 next[ 
  1]= 
  0;  
  int j= 
  0; memset(vis, 
  0, 
  sizeof(vis)); 
  
31                  
  for( 
  int k= 
  2;k<=m;k++) { 
  
32                      
  while(j&&str[i][k]!=str[i][j+ 
  1]) j=next[j]; 
  
33                      
  if(str[i][k]==str[i][j+ 
  1]) j++; 
  
34                     next[k]=j; 
  
35                 } 
  
36                  
  int x=m; 
  
37              
  // 
      for(int k=1;k<=m;k++) printf("%d ",next[k]); printf("\n"); 
  
 
  38  
                   
  while(x) { 
  
39                     
  // 
   if(x==1) break; 
  
 
  40  
                       
  if(!vis[m-next[x]]) 
  
41                     ML[m-next[x]]++; x=next[x];  vis[x-next[x]]= 
  1; 
  
42                 } 
  
43             } 
  
44              
  for( 
  int i= 
  1;i<=m;i++)  
  if(ML[i]==n) { 
  
45                 L=i;  
  break; 
  
46             } 
  
47         }  
  else L= 
  1; 
  
48         next[ 
  1]= 
  0;  
  int j= 
  0; 
  
49          
  for( 
  int i= 
  2;i<=n;i++) { 
  
50              
  while(j&&strcmp(str[i]+ 
  1,str[j+ 
  1]+ 
  1)) j=next[j]; 
  
51  
  // 
              printf("%d %d\n",i,j+1); 
  
 
  52  
               
  if(!strcmp(str[i]+ 
  1,str[j+ 
  1]+ 
  1)) j++; 
  
53            
  // 
    printf("%d %d\n",next[i],j); 
  
 
  54  
              next[i]=j; 
  
55         } 
  
56          
  // 
  printf("%d %d\n",L,n-next[n]); 
  
 
  57  
          printf( 
  " 
  %d\n 
  ",(n-next[n])*L); 
  
58  
  
59     } 
  
60  
  
61      
  return  
  0; 
  
62 }