POJ 2752 C++ （KMP）

#include<iostream>
#include<string>
using namespace std;
int n,next[400008],result[400008];;
char s[400008],t[400008];
void Get_next()
{int j,k;
j=1;
k=0;
next[1]=0;
while(j<=n+1)
       { if(k==0 || s[j]==s[k])
            { j++;
              k++;
              next[j]=k;
             }
          else
             k=next[k];
         }
}
int main()
{ int i,k;
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
   while(scanf("%s",t)!=EOF)
         {n=strlen(t);
          for(i=1;i<=n;i++)
                s[i]=t[i-1];

           s[i]='#';
           Get_next();
           k=0;
           result[k++]=n+1;
           i=n+1;
           while(i!=1)
                { if(next[i]!=1)
                     result[k++]=next[i];
                  i=next[i];
                 }

          for(i=k-1;i>0;i--)
              printf("%d ",result[i]-1);

         printf("%d\n",result[i]-1);                    
     }

   return 0;
}                         

posted on 2008-11-26 01:08 蜗牛 阅读(848) 评论(0)  编辑 收藏 引用 所属分类: ACM ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2008年11月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

常用链接

留言簿(1)

随笔分类(20)

随笔档案(20)

Favorites

搜索

最新评论

阅读排行榜

评论排行榜