HDU - 3336 next运用+递推

题目的匹配应该也要看成一个文本串与另一个模式串的匹配过程

Text是以当前i结尾的后缀来匹配Pattern的前缀(非真)

这里的Pattern肯定是可以匹配成功的,直接由next来保证(next总是当前结尾的最大前缀,恰好满足递推的需要)

(说的不是很准确,就是kmp匹配过程时使用的方法)

举个栗子:

a b a b a c b a

0 0 1 2 3 0 0 1 next

1 1 1 1 1 1 1 1 dp 初始合法状态

1 1 2 2 3 1 1 2 dp 最终计算结果

dp[1] = 1+dp[next[1]] :

    Text a

    Pattern a

dp[2] = 1+dp[next[2]]:

    Text ab

    Pattern ab

dp[3] = 1+dp[next[3]] = 1+dp[1]:

    Text aba

    Pattern aba  a

dp[4] = 1+dp[2]:

    Text abab

    Pattern abab ab

dp[5]  = 1+dp[3]:

    Text ababa

    Pattern ababa aba a

....

dp[8] = 1+dp[1]:

    Text ababacba

    Pattern ababacba a

最终统计得到

4 a

2 ab

2 aba

1 abab

1 ababa

1 ababac

1 ababacb

1 ababacba

这种以【当前状态】来转换角度的统计方法值得学习

所以说动态规划天下第一(明明是递推

/*H E A D*/

int nxt[maxn];

char P[maxn];

int dp[maxn];//dp[i]:P[i]结尾的子串所含满足匹配的前缀的个数

void buildNext(){

	nxt[1]=0;

	int j=0;

	int m=strlen(P+1);

	rep(i,2,m){

		while(j>0&&P[i]!=P[j+1]) j=nxt[j];

		if(P[i]==P[j+1]) j++;

		nxt[i]=j;

		dp[i]=1+dp[j];

	}

}

int main(){

	int t=read();

	while(t--){

		int n=read();

		s1(P);

		dp[0]=0;

		rep(i,1,n) dp[i]=1;

		buildNext();

		ll sum=0;

		rep(i,1,n) sum=(sum+dp[i])%10007;

		println(sum);

	}

	return 0;

}

巴特西

HDU - 3336 next运用+递推

最新文章

热门文章