최 장 공통 답장 하위 문자열 (manacher + hash + 2 점)

4180 단어 문자열

두 문자열 (s1, s2 로 기록) 의 최 장 공공 답장 하위 문자열 을 구하 십시오.
 
해법: 먼저 mnanacher 알고리즘 O (n) 로 s1 꼬치 의 최 장 회 문 서브 꼬치 길이 L 를 처리 하면 마지막 답 은 L, L - 2, L - 4 ~ 0 이 고 우 리 는 p [i] 배열 (i 중심의 최 장 회 문 반지름) 을 구 해 뒤의 2 분 답 판단 에 사용 할 것 이다.
여기에 구덩이 가 하나 있다. 2 분 동안 짝 짓 기 회 문 은 2 분 으로 나 누 어야 한다.2k + 2 길이 의 공공 답장 이 어떻게 있 기 때문이다.틀림없이 2k 길이 의 공공 답장 도 있 을 것 이다. 그러나 2k + 1 길이 의 공공 답장 도 있 을 것 이 라 고 보장 하지 않 는 다.짝 을 나 누 어 토론 하고 싶 지 않다 면 말 수레 를 끄 는 기술 로 모두 기 회 문 으로 바 꿀 수 있다.
  
/* ***********************************************
Author        :pall_scall
Created Time  :2019 04 08      11 53 02 
File Name     :vj.cpp
************************************************ */  
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef unsigned long long ull;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1.0);
char s[maxn<<1],ss[maxn<<1],s1[maxn],s2[maxn],str[maxn<<1];
int p[maxn<<1];
ull hash1[maxn<<1],hash2[maxn<<1],po[maxn<<1];
int len1,len2;
ull geth1(int l,int r){
    if(l == 0) return hash1[r];
    return (ull)(hash1[r]-hash1[l-1]*po[r-l+1]);
}
ull geth2(int l,int r){
    if(l == 0) return hash2[r];
    return (ull)(hash2[r]-hash2[l-1]*po[r-l+1]);
}
int manacher(int len){
    int id = 0,mx = 0;
    int res = 0;
    for(int i = 2; i < len; i++){
        p[i] = mx>i?min(p[2*id-i],mx-i):1;
        while(str[i+p[i]] == str[i-p[i]]) p[i]++;
        if(i+p[i] > mx){
            mx = i+p[i];
            id = i;
        }
        res = max(res,p[i]);
        //printf("%d ",p[i]);
    }
    //cout<mp;
bool judge(int len,int sz){
    mp.clear();
    for(int i = 2; i+len-1 < sz; i+=2){ //      
        if(p[i]-1>=len){ // i                 
            int ra = len/2;  
            int id = i/2-1; //         
            mp[geth1(id-ra,id+ra)] = 1;
            //cout<<1;
        }
    }
    for(int i = 0; i+len-1 < len2; i++){
        if(mp.count(geth2(i,i+len-1))) return true;
    }
    return false;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    po[0] = 1;
    for(int i = 1; i < maxn*2; i++){
        po[i] = po[i-1]*31;
    }
    while(~scanf("%s%s",s1,s2)){
        /*                   */
        len1 = len2 = 0;
        s[len1++] = 'A';
        for(int i = 0; s1[i]!='\0'; i++){
            s[len1++] = s1[i];
            s[len1++] = 'A';
        }
        ss[len2++] = 'A';
        for(int i = 0; s2[i]!='\0'; i++){
            ss[len2++] = s2[i];
            ss[len2++] = 'A';
        }
        /*...........................*/
        /*manacher    */
        int tot = 0;
        str[tot++] = '$';
        str[tot++] = '#';
        for(int i = 0; i < len1; i++){
            str[tot++] = s[i];
            str[tot++] = '#';
        }
        str[tot] = '\0';
        /*...................*/
        /*hash  */
        hash1[0] = s[0];
        for(int i = 1; i < len1; i++)
            hash1[i] = hash1[i-1]*31+s[i];
        hash2[0] = ss[0];
        for(int i = 1; i < len2; i++)
            hash2[i] = hash2[i-1]*31+ss[i];
        /*..........*/
        int l = 0, r = manacher(tot)/2;  
        /*          ，   r s  (       -1)/2，              ，  s      */
        int ans = 0;
        while(l <= r){
            int mid = (l+r)>>1; //      
            if(judge(mid<<1|1,tot)){ 
                l = mid+1;
                ans = mid*2+1;
            }else
                r = mid-1;
        }
        printf("%d
",ans/2);
    }
    return 0;
}

[파이썬 ] 우선순위 큐(우선 순위 대기열)를 위한 heapq모듈 활용법
텐 센트 2020 학교 모집 시험 문제 1 - 압축 알고리즘

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage