KMP 최소 순환 절 문제 해결

\ # 10035. '한 권 에 2.1 연습 1' Power Strings
[제목 설명]
몇 개의 길이 $\ le 10 ^ 6 $의 문자열 을 지정 합 니 다. 각 문자열 은 최대 몇 개의 같은 하위 문자열 로 중복 연결 되 어 있 는 지 물 어보 십시오.예 를 들 어 ababab 는 최대 333 개 ab 로 연결 되 어 있다.
【 알고리즘 】
1. kmp 첫 번 째 단 계 는 문자열 의 특징 벡터 를 구 합 니 다.n%(n-nxt[n])==0&&nxt[n] (n 은 문자열 길이) 의 경우 순환 절 개 수 는 n/(n-nxt[n]) 이 고 모든 위치 에 $i $n%(n-nxt[n])==0&&nxt[n] 의 경우 앞 i 문자 가 순환 합 니 다.2. 문자열 hash 로 순환 절 길 이 를 $l $+ $O (1) $로 판단 할 수 있 습 니 다.
【 코드 】

#include 
using namespace std;
int nxt[1000100];
char s[1000100];
int main() {
    while(~scanf("%s",s+1)&&s[1]!='.') {
        int n=strlen(s+1);
        nxt[1]=0;
        for(int i=2,j=0;i<=n;i++) {
            while(j>0&&(j==n||s[i]!=s[j+1])) j=nxt[j];
            if(s[i]==s[j+1]) j++;
            nxt[i]=j;
        }
        if(n%(n-nxt[n])==0&&nxt[n]) printf("%d
",n/(n-nxt[n]));
        else puts("1");
    }
    return 0;
}

\ # 10045. "한 권 통 2.2 연습 1" 라디오 Transmission
[제목 설명]
문자열 을 드 리 겠 습 니 다. 문자열 이 끊임없이 연결 되 어 있 습 니 다.그러나 이 문자열 은 확실 하지 않 습 니 다. 지금 은 가장 짧 은 길이 가 얼마 인지 만 알 고 싶 습 니 다.
【 알고리즘 】
이 문자열 이 완전 하지 않 을 수 있 기 때문에 순환 문자열 이 아 닌 경우 보완 하 는 것 을 고려 합 니 다. 최소 순환 절 이기 때문에 현재 문자열 의 마지막 문 자 는 반드시 마지막 순환 절 에 있 습 니 다.또한 마지막 문 자 는 일치 하 는 문자열 과 메 인 문자열 과 보 완 된 마지막 문자 의 상대 적 인 위치 가 변 하지 않 기 때문에 $n - nxt [n] $도 최소 순환 절 길이 입 니 다.
【 코드 】

#include 
using namespace std;
int n;
int nxt[1000100];
char s[1000100];
int main() {
    scanf("%d%s",&n,s+1);
    nxt[1]=0;
    for(int i=2,j=0;i<=n;i++) {
        while(j>0&&(j==n||s[i]!=s[j+1])) j=nxt[j];
        if(s[i]==s[j+1]) j++;
        nxt[i]=j;
    }
    int val;
    for(int k=nxt[n];k;k=nxt[k])
        if(k) val=n-k;
    if(n%val) printf("%d
",n/val+1);
    else printf("%d
",n/val);
    return 0;
}

\ # 10046. [1 권 통 2.2 연습 2] OKR - Periods of Words
[제목 설명]
문자열 은 한 정 된 소문 자 시퀀스 입 니 다. 특히 빈 시퀀스 도 하나의 문자열 일 수 있 습 니 다.하나의 직렬 P 는 직렬 A 의 접두사 이 며, 직렬 B 만 존재 할 때 A = PB 입 니 다.P ≠ A 와 P 가 빈 꼬치 가 아니라면 P 는 A 의 proper 접두사 라 고 합 니 다.
Q 를 A 의 주기 로 정의 합 니 다. Q 가 A 의 proper 접두사 이 고 A 는 QQ 의 접두사 입 니 다.예 를 들 어 꼬치 abab 와 ababab 는 모두 꼬치 abababa 의 주기 이다.꼬치 A 의 최대 주 기 는 바로 가장 긴 주기 나 빈 꼬치 (A 가 주기 가 없 을 때) 이다. 예 를 들 어 ababab 의 최대 주 기 는 abab 이다.꼬치 abc 의 최대 주 기 는 빈 꼬치 이다.
모든 접두사 의 최대 주기 길이 의 합 을 구 하 는 문자열 을 보 여 줍 니 다.
【 알고리즘 】
이 문 제 는 최대 주기 인 순환 절 길이 의 최대 치 를 요구한다.그래서 우 리 는 $nxt [i] $배열 이 i 에서 가장 가 까 운 패턴 문자열 위 치 를 기록 하기 때문에 i 에서 가장 멀리 떨 어 진 패턴 문자열 위 치 를 찾 으 면 됩 니 다.아니면 먼저 $nxt [i] = j $의 값 을 계산 한 다음 nxt 배열 을 따라 0 의 이전 까지 계속 찾 아 보 세 요. 하지만 이렇게 하면 T 입 니 다.그래서 우 리 는 다시 하나의 배열 f 를 열 어 i 에서 가장 멀리 떨 어 진 패턴 문자열 의 위 치 를 기록 하고 $f [j] > 0 이면 f [i] = j 그렇지 않 으 면 f [i] = j $로 전달 할 수 있 습 니 다.
【 코드 】

#include 
#define ll long long
using namespace std;
int n;
ll ans;
int nxt[1000100],f[1000100];
char s[1000100];
int main() {
    scanf("%d%s",&n,s+1);
    nxt[1]=0;
    for(int i=2,j=0;i<=n;i++) {
        while(j>0&&(j==n||s[i]!=s[j+1])) j=nxt[j];
        if(s[i]==s[j+1]) j++;
        nxt[i]=j;
        if(f[j]>0) f[i]=f[j];
        else f[i]=j;
        if(f[i]) {
            int len=i-f[i];
            if(i%len==0) ans+=(i/len-1)*len;
            else ans+=i/len*len;
        }
    }
    printf("%lld
",ans);
    return 0;
}

다음으로 전송:https://www.cnblogs.com/Willendless/p/9609445.html