「水」悠悠碧波(KMP)

发布于 2020-07-07  0 次阅读


题目:

帕秋莉掌握了一种水属性魔法
这种魔法可以净化黑暗
帕秋莉发现对于一个黑暗的咒语s,可以使用这个水元素魔法净化它,净化的咒语是一个最长的字符串t,t满足以下条件:
它是s的前缀
它是s的后缀
除前缀和后缀外,它还在s中出现过至少一次
既然你都学会了,那么净化的工作就交给你了!

输入描述:

一行字符串 s ,代表黑暗咒语

输出描述:

一个字符串 t ,表示满足条件的最长净化咒语

样例:

输入:

tqrwantoacthisproblembutqristooweaktodoitqr

输出:

tqr

HINT:

对于60%的数据,s长度≤100
对于100%的数据,s长度≤100,000
保证存在可行的净化咒语

思路:

很明显的KMP算法,没什么好说的,直接求next数组

AC Code:

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
#define N 100009
string s;
int n[N], vis[N];

void getnext(){
    int i=0;
    int j=n[0]=-1;
    while(i<s.length()){
        if((j==-1)||(s[i]==s[j]))
        {
            i++, j++;
            n[i]=j;
        }
        else 
            j=n[j];
    }
}

int main(){
    cin>>s;
    getnext();                              //求next数组
    for(int i=1; i<s.length(); i++)         //将最长相同前缀后缀的长度进行标记
        vis[n[i]]=1;
    int temp=n[s.length()];
    while(temp>0){
        if(vis[temp]){                      //除前缀和后缀外,它还在s中出现过至少一次
            for(int i=0; i<temp; i++)
                cout<<s[i];
            cout<<endl;
            return 0;
        }
        else
            temp=n[temp];     //next[n]不满足,满足的必定为该子串的子串,
    }                         //例如前缀有tqtq,后缀tqtq,中间出现的是tq,则应该输出tqtq的子串tq
    return 0;
}

平平无奇的大学在读本科生