HDU 6153 A SecretA Secret

60 阅读 0 评论 40 点赞

我是靠谱客的博主精明龙猫，最近开发中收集的这篇文章主要介绍HDU 6153 A SecretA Secret，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A Secret

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 256000/256000 K (Java/Others)
Total Submission(s): 4522 Accepted Submission(s): 1581

Problem Description

Today is the birthday of SF,so VS gives two strings S1,S2 to SF as a present,which have a big secret.SF is interested in this secret and ask VS how to get it.There are the things that VS tell:
Suffix(S2,i) = S2[i...len].Ni is the times that Suffix(S2,i) occurs in S1 and Li is the length of Suffix(S2,i).Then the secret is the sum of the product of Ni and Li.
Now SF wants you to help him find the secret.The answer may be very large, so the answer should mod 1000000007.

Input

Input contains multiple cases.
  The first line contains an integer T,the number of cases.Then following T cases.
  Each test case contains two lines.The first line contains a string S1.The second line contains a string S2.
  1<=T<=10.1<=|S1|,|S2|<=1e6.S1 and S2 only consist of lowercase ,uppercase letter.

Output

For each test case,output a single line containing a integer,the answer of test case.
The answer may be very large, so the answer should mod 1e9+7.

Sample Input

aaaaa

abababab

aba

Sample Output

题目描述

给定两个串，求其中一个串T的每个后缀在另一个串S中出现的次数乘以其长度之和。

解题思路

思路：第一个是母串S，第二个子串T是模式串，把字符串S、T反过来，用kmp匹配，

记住，KMP解决的只是匹配问题，关键点在于 S[i]!=T[j]的时候，

ans[j]++ , j= next[j] ，如果依旧是S[i] ！=T[j] ，ans[j]++,直到 j==0结束。

ans[j]就是长度为j的T的子串在S中出现的次数，然后还有就是

这个串T的子串T[0....i ]出现的次数一定要加上它上一个串T[ 0......i+1 ]出现的次数，

因为如果可以匹配后面的，那么前面的也是一定可以匹配的，也就是前面的也是它的子串.

代码更形象，不懂看下代码：

还不懂的话，就是KMP太陌生了。

写法一：

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1000009,mod=1e9 + 7;
char  S[maxn],T[maxn];
int   next[maxn],lenS,lenT;
long  long int ans[maxn];
void  get_next( ){
	  int i=0,j=-1;
	  next[0] = -1;
	  while(  i< lenT){
	  	    if( j==-1 || T[i] == T[j]){
 	    	    next[++i] = ++j;
 	     }
	       else j = next[j];
      }
}
void KMP_Count( ){
	 get_next( );
	 S[lenS]='#';
	 int j=0;
	 for( int i=0;i<=lenS;i++){
	       while( j && S[i] !=T[j] ){
		  	     ans[j]++;
		  	     j=next[j];
		  }
		  if( S[i] == T[j] ){
	      	  j++;
	      	  if( j == lenT ){
	      	  	  ans[lenT]++;
	      	  	  j = next[j];
		       }
		   }
	  }
	 long long int sum = 0;
	 for( int i = lenT;i>=0;i--){
	 	  ans[i]+=ans[i+1];
	 	  sum = (sum % mod + ( ( ans[i] % mod ) * (i%mod) )%mod ) % mod;
	 }
	 printf("%lldn",sum);
}
int main(void){
	int t;
	scanf("%d",&t);
	while( t--){
		  memset(S,0,sizeof(S));
		  memset(T,0,sizeof(T));
		  memset(ans,0,sizeof(ans));
		  scanf("%s",S);
		  scanf("%s",T);
		  strrev( S );
		  strrev( T );
		  lenS = strlen( S );
		  lenT = strlen( T );
		  KMP_Count();
	}
	
	return 0;
}

写法二：

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1000009,mod=1e9 + 7;
char  S[maxn],T[maxn];
int   next[maxn],lenS,lenT;
long  long int ans[maxn];
void  get_next( ){
	  int i=0,j=-1;
	  next[0] = -1;
	  while(  i< lenT){
	  	    if( j==-1 || T[i] == T[j]){
 	    	    next[++i] = ++j;
 	     }
	       else j = next[j];
      }
}
void KMP_Count( ){
	 get_next( );
	 int i=0,j=0;
	 while( i<lenS && j<lenT   ){
	 	    if( j==-1 || S[i] == T[j] ){
	 	    	 i++;
				 j++;
				 if( j == lenT ){
				 	 ans[j]++;
				 	 j =  next[j]; 
				 } 
			 }
			 else { 
			        ans[ j ]++;
			 	    j =next[j];
		 	 }
	 }  
	 while( j && S[i] !=T[j] ){
	 	    ans[j]++;
	 	    j = next[j];
	 }
	 long long int sum = 0;
	 for( i = lenT;i>=0;i--){
	 	  ans[i]+=ans[i+1];
	 	  sum = (sum % mod + ( ( ans[i] % mod ) * (i%mod) )%mod ) % mod;
	 }
	 printf("%lldn",sum);
}
int main(void){
	int t;
	scanf("%d",&t);
	while( t--){
		  memset(S,0,sizeof(S));
		  memset(T,0,sizeof(T));
		  memset(ans,0,sizeof(ans));
		  scanf("%s",S);
		  scanf("%s",T);
		  strrev( S );
		  strrev( T );
		  lenS = strlen( S );
		  lenT = strlen( T );
		  KMP_Count();
	}
    return 0;
}