HDU 2594 EX_KMP或者字符串hash

题意：给你2个字符串a , b 。问 a的前缀和b的后缀的公共部分最长是多少。

思路：把a从前往后hash，把b从后往前hash，如果hash值相等，那么代表两个字符串相等，那么更新长度。

最后输出这个长度的最大值即可。

还可以用EX_KMP搞，我们可以把两个字符串连成一个，然后根据EX_KMP的NEXT数组的作用，直接就可以判断后缀是否等于前缀。

先来一发HASH的代码。

#include <set>#include <map>#include <stack>#include <cmath>#include <queue>#include <cstdio>#include <string>#include <vector>#include <iomanip>#include <cstring>#include <iostream>#include <algorithm>#define Max 2505#define FI first#define SE second#define ll long long#define PI acos(-1.0)#define inf 0x3fffffff#define LL(x) ( x << 1 )#define bug puts("here")#define PII pair<int,int>#define RR(x) ( x << 1 | 1 )#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;#define N 111111int Next[N] ;char b[N] ;void EX_Next(){    int x = 0 ;    int l = strlen(b) ;    Next[0] = l ;    while(x < l - 1 && b[x] == b[x + 1])x ++ ;    Next[1] = x ;    x = 1 ;    for (int k = 2 ; k < l ; k ++ ){        int p = x + Next[x] - 1 , L = Next[k - x] ;        if(k - 1 + L >= p){            int j = (p - k + 1) > 0 ? (p - k + 1) : 0 ;            while(k + j < l && b[k + j] == b[j]) j ++ ;            Next[k] = j ;            x = k ;        }else {            Next[k] = L ;        }    }}int main() {    while(scanf("%s",b) != EOF){        int l = strlen(b) ;        scanf("%s",b + l) ;        EX_Next() ;        int l1 = strlen(b) ;int ans = -1 ;        for (int i = l ; i < l1 ; i ++ ){            int now = Next[i] ;            if(i + now == l1)                ans = max(ans , now ) ;        }        ans = ans >= l ? l : ans ;        for (int i = 0 ; i < ans ; i ++ )cout << b[i] ;        if(ans == -1)cout << 0 << endl ;        else cout << " " << ans << endl;    }    return 0;}