POJ2774 Long Long Message

发表于 | 分类于 |
字数统计: 283 字

题目地址

题解

就是求最长公共子串
哈希+排序+二分=暴力卡过
哈希要用unsigned long long，用unsigned int极其容易撞车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef unsigned long long ui;
char a[200005],b[200005];
ui P=1000000007,list[200005],h1[200005],h2[200005],pow1[200005];
int l1,l2;
bool check(int c){
    int i,j;ui t;
    for(i=1;i<=l1-c+1;i++)
        list[i-1]=h1[i+c-1]-h1[i-1]*pow1[c];
    sort(list,list+l1-c);
    for(i=1;i<=l2-c+1;i++){
        t=h2[i+c-1]-h2[i-1]*pow1[c];
        if((*lower_bound(list,list+l1-c,t))==t)
            return true;
    }
    return false;
}
int main(){
    scanf("%s%s",a,b);
    l1=strlen(a),l2=strlen(b);
    int i,j,l,r,md;
    for(pow1[0]=1,i=1;i<=200000;i++)
        pow1[i]=pow1[i-1]*P;
    for(i=1;i<=l1;i++)
        h1[i]=h1[i-1]*P+a[i-1];
    for(i=1;i<=l2;i++)
        h2[i]=h2[i-1]*P+b[i-1];
    l=0,r=min(l1,l2);
    //用b匹配a 
    while(l<r){
        md=l+(r-l+1)/2;
        if(check(md))
            l=md;
        else r=md-1;
    }
    printf("%d\n",r);
    return 0;
}