KMP板子+Trie板子

KMP算法是一个字符串匹配算法，最直白的用法就是在一个长度为n的字符串T中查找另一个长度为m字符串P的匹配（总之就是用于文本中进行单个字符串的匹配）。

对于这个问题，暴力算法是很好做的，直接对于T的每个位置判断一下当前位置作为P的结尾是否可以匹配成功，算法复杂度是O(nm)。

KMP算法的主要思想是：假设现在正在用P的第j个字符和T的第i个字符进行匹配，如果成功就匹配下一个字符；如果失败的话就跳到以j-1个字符为结尾的后缀的最长相同前缀的结尾后一个位置进行匹配。为此要把P做成一个状态机（也就是失配函数），在上面根据情况进行转移。

复杂分析：每一次i增加的时候伴随着j的增加，i增加的时候为j提供了减少的空间，因此j最多会减少n次。加上预处理的时间，总时间复杂度O(n+m)。（这次一定要好好记住，之前看一次忘一次。。。）

下面给出上面问题的代码（n<=1000000,m<=10000）。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 #include<vector>

 #include<cctype>

 using namespace std;

 const int maxn=;

 const int maxm=;

 int N,f[maxn];

 char P[maxm],T[maxn];

 void getfail(char *p)

 {

     f[]=f[]=;

     int m=strlen(p);

     for(int i=;i<m;i++){

         int j=f[i];

         while(j&&p[i]!=p[j]) j=f[j];

         f[i+]=p[i]==p[j]?j+:;

     }

 }

 int find(char *t,char *p)

 {

     getfail(p);

     int j=,re=,m=strlen(p),n=strlen(t);

     for(int i=;i<n;i++){

         while(j&&t[i]!=p[j]) j=f[j];

         if(t[i]==p[j]) j++;

         if(j==m) re++,j=f[j];

     }

     return re;

 }

 int main()

 {

     scanf("%d\n",&N);

     for(int i=;i<=N;i++){

         gets(P);gets(T);

         printf("%d\n",find(T,P));

     }

     return ;

 }

Trie是一种可以让你欢快的在字典中查找单词的数据结构，所以单次查询时间复杂度为什么是O(1)。。。。。。

下面的代码是这样一个问题：给出一个长字符串和一些字典中的单词，问用这些单词拼接出长字符串的方案数mod20071027答案是多少，单词可以重复使用。倒着插入所有字典之后dp就可以了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 #include<vector>

 #include<cctype>

 using namespace std;

 const int maxn=;

 const int maxm=;

 const int mo=;

 int N,f[maxn];

 char T[maxn],S[maxm];

 struct Trie{

     static const int maxnd=;

     static const int sigma_size=;

     int np,ch[maxnd][sigma_size],val[maxnd];

     Trie(){ np=,val[]=; memset(ch[],,sizeof(ch[])); }

     void insert(char *s)

     {

         int now=,i=strlen(s)-;

         while(i>=){

             if(!ch[now][s[i]-'a']){

                 ch[now][s[i]-'a']=++np;

                 memset(ch[np],,sizeof(ch[np]));

                 val[np]=;

             }

             now=ch[now][s[i--]-'a'];

         }

         val[now]++;

     }

     int find(int i)

     {

         int now=,re=;

         while(i>){

             if(!ch[now][T[i]-'a']) break;

             now=ch[now][T[i--]-'a'];

             if(val[now]) re=(re+f[i])%mo;

         }

         if(!i&&val[ch[now][T[i]-'a']]) re=(re+)%mo;

         return re;

     }

 }trie;

 void data_in()

 {

     gets(T); scanf("%d\n",&N);

     for(int i=;i<=N;i++){

         gets(S);

         trie.insert(S);

     }

 }

 void work()

 {

     int n=strlen(T);

     for(int i=;i<n;i++) f[i]=trie.find(i);

     printf("%d\n",f[n-]);

 }

 int main()

 {

     data_in();

     work();

     return ;

 }

巴特西

KMP板子+Trie板子

最新文章

热门文章