1087: Common Substrings

Time Limit:3000/1000 MS (Java/Others) Memory Limit:163840/131072 KB (Java/Others)
Total Submissions:857 Accepted:112

[Submit][Status][Discuss]

Description

You are given two long strings A

and B. They are comprised of lowercase letters. You should compute how many suffixes of A are the prefixes of B

Input

In the first line is a number T

(0<T≤100

) , indicating the cases following.

In the next T lines each line contains two strings — A

and B

( 0<|A|≤105,0<|B|≤105

)

Output

There should be exactly T

lines.

Each line contain a number — the answer.

Sample Input

1

abcc ccba

Sample Output

HINT

In the first case, cc and c are two of the suffixes of string A, and they are the prefixes of string B.

【分析】H[i]-H[L]*xp[L]表示从s[i]开始的长度为L的字符串的哈希值。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

using namespace std;

typedef long long ll;

const ll N = 1e5+;

const int x=;

ll H1[N],H2[N],xp[N];

ll hs1,hs2;

int ans;

char stra[N],strb[N];

int main()

{

    int T;

    scanf("%d",&T);

    while (T--){

        scanf("%s%s",stra,strb);

        int lena=strlen(stra),lenb=strlen(strb);

        H1[lena]=,H2[lenb]=;

        for (int i=lena-;i>=;--i)

            H1[i]=H1[i+]*x+(stra[i]-'a');

        for (int i=lenb-;i>=;--i){

            H2[i]=H2[i+]*x+(strb[i]-'a');

        }

        xp[]=;

        ans=;

        for (int i=;i<=max(lena,lenb);++i)

            xp[i]=xp[i-]*x;

        for (int L=;L<=min(lena,lenb);++L){

            hs2=H2[]-H2[L]*xp[L];

            hs1=H1[lena-L]-H1[lena]*xp[L];

            if (hs2==hs1)

                ans++;

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

1087: Common Substrings （哈希）