首页 > 代码库 > [日常训练]article

[日常训练]article

2024-08-19 22:54:42   220人阅读

Description

小技术分享今天来写作文啦！
小技术分享非常善于堆砌辞藻。在洋洋洒洒写了一长篇之后，小技术分享发现作文中很多段落都似曾相识。小技术分享认为，如果一段字符在文章开头，结尾和中间都出现过，那么这段字符就可以被认为是一个“经典段”。
现在小技术分享给你一篇文章，他想知道最长的一段“经典段”长度是多少？
注意，这里要求经典串至少出现三次，分别作为文章的前缀，后缀，及既非前缀也非后缀。

Input

一行，给出一个由小写字母组成的字符串。

Output

输出满足题目要求的非空子串，如果不存在这样的非空子串输出技术分享。（字符串严格匹配，不含双引号）

Sample Input

fixprefixsuffix

Sample Output

fix

HINT

字符串长度技术分享。

Solution

技术分享预处理出这个字符串技术分享能与后缀匹配的前缀最长子串技术分享.

用技术分享数组求出技术分享中哪些下标技术分享使得技术分享为技术分享后缀.

技术分享匹配技术分享和技术分享,求出最大的技术分享使得技术分享为技术分享后缀.

#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1000005
using namespace std;
int nxt[N],n,ans;
bool f[N];
char a[N],b[N],c[N];
inline void get_nxt(char b[],int n){
    for(int i=2,j=0;i<=n;++i){
        while(j&&b[j+1]!=b[i]) j=nxt[j];
        if(b[j+1]==b[i]) ++j;
        nxt[i]=j;
    }
}
inline void kmp1(){
    int k=0;
    for(int i=1,j=0;i<n;++i){
        while(j&&b[j+1]!=a[i]) j=nxt[j];
        if(b[j+1]==a[i]) ++j;
        if(i==n-1) k=j;
    }
    while(k){
        //printf("k=%d\n",k); 
        f[k]=true;k=nxt[k];
    }
}
inline int kmp2(){
    int ret=0;get_nxt(a,n);
    for(int i=2,j=0;i<n;++i){
        while(j&&c[j+1]!=c[i]) j=nxt[j];
        if(c[j+1]==c[i]) 
            if(f[++j]) ret=max(ret,j);
    }
    return ret;
}
inline void print(){
    printf("Y can‘t find any classical string.\n");
}
inline void init(){
    scanf("%s",c+1);n=strlen(c+1);
    if(n<3){
        print();return;
    }
    for(int i=n,j=1;i>1;--i,++j)
        b[j]=c[i];
    for(int i=n-1,j=1;i;--i,++j)
        a[j]=c[i];
    get_nxt(b,n-1);kmp1();
    ans=kmp2();
    if(ans){
        for(int i=ans;i;--i)
            printf("%c",b[i]);
        printf("\n");
    }
    else print();
}
int main(){
    freopen("article.in","r",stdin);
    freopen("article.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

[日常训练]article


联系
我们