HDU 5763 Another Meaning-白红宇

HDU 5763 Another Meaning

阅读量：6279 次

发布时间：2019-06-22

本文共 919 字，大约阅读时间需要 3 分钟。

简单dp+KMP。记dp[i]为以0--i能表达的意义种类。

如果以s[i]为结尾的后缀不匹配，那么dp[i]=dp[i-1]。

如果以s[i]为结尾的后缀匹配，那么dp[i]=dp[i-1]+dp[i-len]; （即表达第一种意思的种类数+表达第二种意思的种类数）

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}inline int read(){ char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x;}LL mod=1000000007;const int maxn=100010;int nx[maxn],f[maxn];char a[maxn],b[maxn];int len1,len2;LL ans[maxn];void get_next(){ int j=-1,i=0; nx[0]=-1; while(i