题意：给定一个句子str，和一个单词sub，这个单词sub可以翻译成两种不同的意思，问这个句子一共能翻译成多少种不能的意思
例如：str:hehehe sub:hehe 那么，有**he、he**、和hehehe三种不同的意思，
考虑一下aaadaaa这种情况？sub：aa 前面的aaa有三种，后面的aaa有三种，所以一共应该是有9种情况。
可以考虑成3*3=9
如果你考虑分块去相乘的话，那么恭喜你，你GG了。因为这样写非常复杂，而且非常难判断。
可以考虑下dp，因为注意到，它每个单词只有两种状态，要么转换成其他意思，要么就保留原意。
记dp[i]为匹配到str的第i个字符，所拥有的方案数，那么，如果不转换意思，dp[i] = dp[i-1]
就是方案数是没增加的，还是原来拥有的总数。
那么考虑转义。需要str[i-lensub+1...i]这段字符和sub一模一样，你才能转义把？
这里可以用字符串hash的方法O（1）判断
那么dp[i] += dp[i-lenstub];
就是在屏蔽str[i-lensub+1...i]这段字符的情况下，拥有的方案数，+我的转义，就是一种全新的方案，所以匹配到这个字符的时候，方案数要加上屏蔽这段字符前拥有的方案数
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
typedef unsigned long long int ULL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 100000 +20;
char str[maxn];
char sub[maxn];
LL dp[maxn];
const int MOD = 1e9+7;
ULL sumhash[maxn];
ULL powseed[maxn];
const int seed = 131;
ULL calc (int begin,int end)
{
return sumhash[end] - powseed[end-begin+1]*sumhash[begin-1];
}
int f;
void work ()
{
scanf("%s%s",str+1,sub+1);
int lenstr = strlen(str+1);
int lensub = strlen(sub+1);
ULL sub_hash = 0;
for (int i=1;i<=lensub;++i) sub_hash = sub_hash*seed + sub[i];
for (int i=1;i<=lenstr;++i) sumhash[i] = sumhash[i-1]*seed + str[i];
for (int i=0;i<=lensub;++i) dp[i]=1;
// printf ("%I64u\n",sub_hash);
// printf ("%I64u\n",sumhash[4]);
for (int i=lensub;i<=lenstr;++i)
{
dp[i] = dp[i-1];
//printf ("%d %d %I64u\n",i-lensub+1,i,calc(i-lensub+1,i));
if (calc(i-lensub+1,i) == sub_hash)
{
dp[i] += dp[i-lensub];
}
dp[i] %= MOD;
}
printf ("Case #%d: %I64d\n",++f,dp[lenstr]);
return ;
}
int main()
{
#ifdef local
freopen("data.txt","r",stdin);
#endif
powseed[0]=1;
for (int i=1;i<=maxn-20;++i) powseed[i] = powseed[i-1]*seed;
int t;
scanf("%d",&t);
while (t--) work();
return 0;
} View Code
这题也可以用kmp做的
就是kmp匹配一次后，用个isok数组保存str的第i位能否匹配成功就可以了
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
typedef unsigned long long int ULL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 100000 +20;
char str[maxn];
char sub[maxn];
LL dp[maxn];
bool isok[maxn];
const int MOD = 1e9+7;
int f;
void get_next (char sub[],int nextliu[],int len)
{
int i=1,j=0;
nextliu[1]=0;//记得初始值不能忘记
//next[len+1]这个也有值了 后面的++i和++j先加后赋值
while (i<=len)
{
//sub[i]的含义，后缀的单个字符
//sub[j]的含义，前缀的单个字符
if (j==0 || sub[i]==sub[j])//考虑的是上一个的
{
nextliu[++i]=++j; //用是上一个的比较，值的当前的值
}
else j=nextliu[j];
}
return ;
}
int nextliu[maxn];
int kmp (char str[],char sub[],int pos)
{
int len1=strlen(str+1);
int len2=strlen(sub+1);
//int next[maxn]={0};//maxn为最大长度
get_next(sub,nextliu,len2);//得到next[]数组
int i=pos;//从哪里出发
int j=1;
int ans=0;
while (i<=len1)
{
if (j==0 || str[i]==sub[j])
{
i++;j++;
}
else j=nextliu[j];
if (j==len2+1)//有一个了
{
isok[i-1]=1; //标记这个位置是OK的
ans++;
j=nextliu[j];//回溯匹配
//i值不用回溯的
}
}
return ans;
}
void work ()
{
scanf("%s%s",str+1,sub+1);
int lenstr = strlen(str+1);
int lensub = strlen(sub+1);
memset(isok,0,sizeof isok);
kmp(str,sub,1);
for (int i=0;i<=lensub;++i) dp[i]=1;
// for (int i=1;i<=lenstr;++i)
// {
// printf ("%d ",isok[i]);
// }
// printf ("\n");
for (int i=lensub;i<=lenstr;++i)
{
dp[i]=dp[i-1];
if (isok[i]) dp[i] += dp[i-lensub];
dp[i] %= MOD;
}
printf ("Case #%d: %I64d\n",++f,dp[lenstr]);
return ;
}
int main()
{
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d",&t);
while (t--) work();
return 0;
} View Code
Count the string
HDU - 3336
统计所有前缀在本串中出现的次数和
kmp + dp
利用next数组。
给定一个长为lenstr(<=20W)的字符串，要求找出所有前缀在本串中出现的次数，在这里前缀有,"a","ab","aba","abab" ans=2+2+1+1=6。思路：利用next[]的意义，最大的前缀和后缀匹配，那么，设dp[i]表示以第i个字符串结尾的所有子串（记住一定要是第i个字符串结尾，不要以为dp[n]就是答案，子串还有很多），和前i个字符的前缀(前缀一定是:s[1],s[1]s[2],s[1]s[2]s[3]，这样的，不能是s[2]s[3]这样的。)所匹配的数目。那么，既然前缀和后缀相同，abab*****abab,那么，我的dp[i]=dp[next[i+1]-1]+1。（+1）是为了加上自己那个串，出现了一次。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (1<<28)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int MOD = 10007;
const int maxn = 200000+20;
char str[maxn];
void get_next (char sub[],int nextliu[],int len)
{
nextliu[1]=0;
int i=1,j=0;
while (i<=len)
{
if (j==0 || sub[i]==sub[j])
{
nextliu[++i]=++j;
}
else j=nextliu[j];
}
return ;
}
int nextliu[maxn];
int dp[maxn]={0};
void work ()
{
int lenstr;
scanf ("%d",&lenstr);
scanf ("%s",str+1);
get_next(str,nextliu,lenstr);
/*
for (int i=1;i<=lenstr;i++)
{
printf ("%d ",next[i]);
}
printf ("\n");*/
int ans=0;
for (int i=1;i<=lenstr;i++)
{
dp[i]=dp[nextliu[i+1]-1]+1;
ans += dp[i];
ans %= MOD;
}
printf ("%d\n",ans);
return ;
}
int main ()
{
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf ("%d",&t);
while (t--)
{
work ();
}
return 0;
}