문자열 hash + 2 분 답 - 최 장 공통 문자열 구하 기 - poj 2774

Long Long Message
Problem's Link： http://poj.org/problem?id=2774
 
Mean: 
 두 문자열 의 가장 긴 공통 문자열 의 길 이 를 구 합 니 다.
analyse:
 앞에서 접미사 배열 을 배 울 때 이미 한 번 했 지만, 지금 은 주공 격 문자열 hash 를 문자열 hash 로 다시 한 번 쓰 고 있 습 니 다.
이 문제 의 사고방식 은 이렇다.
1) 비교적 짧 은 꼬치 의 길 이 를 하 이 로 한 다음 에 2 분 의 답 (매번 길이 가 mid = (low + high) > > 1 이 존재 하 는 지 여 부 를 판단 하고 존재 하면 하 계 를 증가 하 며 존재 하지 않 으 면 상 계 를 축소 한다).
2) 주로 답 에 대한 판단 (judge 함수).구체 적 으로 코드 주석 을 참조 하 세 요.
Time complexity：O(n)
 
Source code：
 

// Memory   Time
// 1347base     0MS
// by : Snarl_jsb
// 2014-10-04-21.16
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define ULL unsigned long long
using namespace std;

string s1,s2;
int l1,l2,seed=131;
vector<ULL> hash;
bool judge(int x)
{
    hash.clear();
    ULL tmp=0;
    for (int i = 0; i < x; i++)
    {
        tmp=tmp* seed + s1[i];
    }
    hash.push_back(tmp);
    ULL base =1;
    for (int i = 1; i < x; i++)
    {
        base *= seed;
    }
    for (int i = x; i < l1; i++)
    {
        tmp=(tmp*seed+s1[i])-base*s1[i-x]*seed;
        hash.push_back(tmp);
    }
    sort(hash.begin(),hash.end());
    ULL hashval = 0;
    for (int i = 0; i < x; i++)
    {
        hashval = hashval * seed + s2[i];
    }
    if (binary_search(hash.begin(),hash.end(),hashval))
        return 1;
    for (int i = x; i < l2; i++)
    {
        hashval = (hashval-(s2[i-x])*base)*seed+s2[i];
        if (binary_search(hash.begin(),hash.end(),hashval))
            return 1;
    }
    return 0;
}
int main()
{
    while (cin>>s1>>s2)
    {
        l1=s1.size();
        l2=s2.size();
        int ans = 0;
        int high = min(l1,l2);
        int low = 0;

        while (low <= high)
        {
            int mid = (low+high)>>1;
            if (judge(mid))
            {
                ans = mid;
                low = mid+1;
            }
            else
                high = mid-1;
        }
        printf("%d
",ans);
    }
    return 0;
}

설명 코드:

// Memory   Time
// 1347k     0MS
// by : Snarl_jsb
// 2014-10-04-21.16
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define ULL unsigned long long
using namespace std;

string s1,s2;
int l1,l2,seed=131;
vector<ULL> hash;
bool judge(int x)
{
    hash.clear();//               
    //  s1  hash 
    ULL tmp=0;
    for (int i = 0; i < x; i++)
    {
        tmp=tmp* seed + s1[i];
    }
    hash.push_back(tmp);
    ULL base =1;
    for (int i = 1; i < x; i++)//    x base 
    {
        base *= seed;
    }
    for (int i = x; i < l1; i++)
    {
        tmp=(tmp*seed+s1[i])-base*s1[i-x]*seed;
        hash.push_back(tmp);
    }
    //    
    sort(hash.begin(),hash.end()); //      ，     
    ULL hashval = 0;
    for (int i = 0; i < x; i++)//  s2 0 x hash 
    {
        hashval = hashval * seed + s2[i];
    }
    if (binary_search(hash.begin(),hash.end(),hashval))//  s2 0 x hash    s1  hash  
        return 1;
    for (int i = x; i < l2; i++)//     s2 0 x hash      ，      s2    x hash      s1  hash  
    {
        hashval = hashval*seed+s2[i]-s2[i-x]*base*seed;
        if (binary_search(hash.begin(),hash.end(),hashval))
            return 1;
    }
    return 0;
}
int main()
{
    while (cin>>s1>>s2)
    {
        l1=s1.size();
        l2=s2.size();
        int ans = 0;
        int low=0,high = min(l1,l2);
        while (low <= high)//    
        {
            int mid = (low+high)>>1;
            if (judge(mid))//        
            {
                ans = mid;
                low = mid+1;
            }
            else
                high = mid-1;
        }
        printf("%d
",ans);
    }
    return 0;
}