hdu - 4333 - Revolving Digits - 확장 kmp

확 장 된 KMP 알고리즘 입 니 다. 이 알고리즘 은 KMP 의 확장 으로 KMP 를 포함 하고 있 습 니 다.이것 은 한 그룹의 수 치 를 구 했 습 니 다. extend [i] 는 A 문자열 에서 i 로 시작 하 는 접미사 (i 에서 lena 까지 의 문자열) 와 B 문자열 의 가장 긴 공공 접두사 (처음부터 다른 문자 까지) 의 길 이 를 표시 합 니 다. 즉, LCP 입 니 다.next [i] 는 T [i. m] 와 T 의 가장 긴 공공 접두사 길이, 즉 자체 적 으로 일치 하 는 길 이 를 나타 낸다.extend [0. k - 1] 을 설정 한 것 은 이미 계산 되 었 으 며, 이전의 일치 과정 에서 도착 한 가장 먼 위 치 는 p - 1 이다.가장 먼 위 치 는 엄 격 히 말 하면 i + extend [i] - 1 의 최대 치 입 니 다. 그 중에서 i = 0, 1, 2, 3,..., k - 1;최대 값 을 설정 한 i 는 a 입 니 다.A [a ~ p - 1] = B [0 ~ p - a - 1], A [k ~ p - 1] = B [k - a ~ p - 1 - a], 령 L = next [k - a], k + L < p 가 있 으 면 extend [k] = L 을 출시 할 수 있 습 니 다. 그렇지 않 으 면 A [p] 와 B [p - k] 를 계속 판단 하고 같 지 않 을 때 까지 extend [k] 와 a 값 을 업데이트 해 야 합 니 다.
http://acm.hdu.edu.cn/showproblem.php?pid=4333

void build_next()
{
    int k, q, p, a;
    next[0] = len_t;
    for (k = 1, q = -1; k < len_t; k ++, q –)
    {
        if (q < 0 || k + next[k - a] >= p)
        {
            if (q < 0)q = 0, p = k;
//q B          ，p A          ，            +1
//q         1，      B       
            while (p < len_t && T[p] == T[q])
            {
                p ++, q ++;
            }
            next[k] = q, a = k;
        }
        else
        {
            next[k] = next[k - a];
        }
    }
}
void extend_KMP()
{
    int k, q, p, a;
    for (k = 0, q = -1; k < len_s; k ++, q –)
    {
        if (q < 0 || k + next[k - a] >= p)
        {
            if (q < 0)q = 0, p = k;
            while (p < len_s && q < len_t && S[p] == T[q])
            {
                p ++, q ++;
            }
            extend[k] = q, a = k;
        }
        else
        {
            extend[k] = next[k - a];
        }
    }
}

문제 풀이:
이 문제 의 중점 은 x 가 디지털 교대 후의 모든 수 와 x 의 크기 관 계 를 비교 하 는 것 이다.x 가 매우 크기 때문에 우 리 는 x 와 교대 후의 모든 수 를 x 길이 의 문자열 로 보고 문자열 을 비교 해 야 한다.즉, 우 리 는 x 뒤에 x 를 연결 하여 xx 로 바 꾼 다음 에 xx 앞 n 위 가 모든 시작 길이 가 n 인 문자열 과 xx 앞 n 위의 크기 를 비교 할 수 있다.만약 에 우리 가 xx 의 모든 사람과 xx 의 가장 긴 공공 접두사 의 길 이 를 빨리 구 할 수 있다 면 크기 를 비교 할 수 있다 면 우 리 는 O (1) 의 시간 만 필요 하고 모든 사람의 가장 긴 공공 접 두 사 를 구 할 수 있다. 확장 KMP 알고리즘 을 사용 하여 O (n) 시간 안에 구 할 수 있다. 그러면 O (n) 시간 안에 모든 비 교 를 완성 할 수 있다.
비교 하 는 것 을 제외 하고 본 문 제 는 숫자 에 대해 심 도 를 해 야 한다. 관찰 을 통 해 우 리 는 반복 되 는 숫자 가 나타 나 는 상황 은 원래 의 x 에 순환 절 이 존재 한 다 는 것 을 설명 한다. 우 리 는 x 의 최소 순환 절 을 찾 은 다음 에 순환 절 안의 숫자 만 비교 하면 된다.그리고 최소 순환 절 을 구 하 는 것 도 KMP 알고리즘 이나 KMP 알고리즘 을 확장 하여 얻 을 수 있 습 니 다. 그러면 전체 시간 복잡 도 는 O (n) 입 니 다.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cstring>
#include<set>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int N=200005;
char s[N];
int next[N];//next                             
//                                     
void getnext(int n)
{
    int l=1,r=-1;//l   r           
    next[0]=0;
    for(int i=1;i<n;++i)
    {//next[i]  s s[i..n]          
        if(i+next[i-l]<=r)
        {
            next[i]=next[i-l];//                                      r           copy  
        }else
        {
            int j=max(r-i+1,0);//                                     
            for(;j+i<2*n;++j)
            if(s[j]!=s[i+j])
            break;
            next[i]=j;
            l=i;
            r=i+j-1;
        }
    }
}
int main()
{
   int T;
   //freopen("data.txt","r",stdin);
   scanf("%d",&T);
   getchar();
   for(int c=1;c<=T;++c)
   {
        gets(s);
        int n=strlen(s);
        for(int i=0;i<n;++i)
        {
            s[i+n]=s[i];
        }
        s[n*2]=0;//copy2
        
        getnext(n);
        
        int i;
        for(i=1;i<n;++i)
            if(i+next[i]>=n)
                break;//          
        
        int m=(n%i)?m:i;//               
        int l=0,q=1,g=0;
        for(i=1;i<m;++i)
        {
            if(next[i]>=n)
            {
                ++q;
            }
            else if(s[next[i]]>s[i+next[i]])
            {
                ++l;
            }else
            {
                ++g;
            }
        }
        printf("Case %d: %d %d %d
",c,l,q,g);
   }
   return 0;
}