Light OJ 1334 Genes in DNA KMP+DP

題目來源：Light OJ 1334 Genes in DNA

題意：輸入文本串和模式串 模式串的前綴和後綴組成(n-1)*(n-1)個組合 求模式串的子串出現多少次前後綴組合 一個子串可以對應多個組合串

思路：既然是前綴和後綴的組合 很好想到正反求2次KMP 枚舉相鄰的2個字符 i,j 答案就是若干以i結尾的前綴數量乘以j為開始的後綴數量的積的和

求到i字符為止的前綴數量和HDU 3336差不多 有點DP的思想

求以j字符開始的後綴數就是發過來 然後和求前綴一樣的

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 50010;
int l[maxn], r[maxn], f[maxn];
int dp1[maxn], dp2[maxn];
char s1[maxn], s2[maxn];
void getFail(char *p, int *dp)
{
	int m = strlen(p);
	f[0] = f[1] = 0;
	dp[0] = 0;
	dp[1] = 1;
	for(int i = 1; i < m; i++)
	{
		int j = f[i];
		while(j && p[i] != p[j])
			j = f[j];
		f[i+1] = p[i] == p[j] ? j+1 : 0;
		dp[i+1] = p[i] == p[j] ? dp[j+1]+1 : 1;
	}
}
void find(char *s1, char* s2, int* dp, int* a)
{
	int cnt = 0;
	int j = 0;
	int n = strlen(s1);
	int m = strlen(s2);
	for(int i = 0; i < n; i++)
	{
		while(j && s1[i] != s2[j])
			j = f[j];
		if(s1[i] == s2[j])
			j++;
		a[i+1] = dp[j];
		if(j == m)
		{
			a[i+1]--;
			j = f[j];
		} 
	}
}


int main()
{
	int cas = 1;
	int T;
	scanf("%d", &T);
	while(T--)
	{
		
		scanf("%s %s", s1, s2);
		int n = strlen(s1);
		int m = strlen(s2);
		getFail(s2, dp1);
		find(s1, s2, dp1, l);
		reverse(s1, s1+n);
		reverse(s2, s2+m);
		getFail(s2, dp2);
		find(s1, s2, dp2, r);
		long long ans = 0;
		for(int i = 1; i < n; i++)
		{
			ans += (long long)l[i]*r[n-i];
		}
		printf("Case %d: %lld\n", cas++, ans);
	}
	return 0;
}