首页 > ACM题库 > HDU-杭电 > HDU 4763-Theme Section-KMP-[解题报告]HOJ
2015
09-17

HDU 4763-Theme Section-KMP-[解题报告]HOJ

Theme Section

问题描述 :

It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a ‘theme section’. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of ‘EAEBE’, where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters ‘a’ – ‘z’.

To get well prepared for the festival, the hosts want to know the maximum possible length of the theme section of each song. Can you help us?

输入:

The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6.

输出:

The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6.

样例输入:

5
xy
abc
aaa
aaaaba
aaxoaaaaa

样例输出:

0
0
1
1
2

题意是在一个字符串中找出一个前缀一个后缀和一个中间的子串,互相不重叠并且三部分完全一样

运用的是exKMP

对自身求一个next数组

next[i]表示以i为开始位置的子串与整个串的前缀最长匹配到多少长度

然后就是枚举了

首先求一个可能存在的最大长度。

在一个位置i中,如果要满足要求,子串的最大长度不能超过 min(i,  next[i], (len – i) / 2);

所有的最大长度的最大值就是可能存在的最大长度

最后对后三分之一的位置,看next[i]是否不超过这个最大长度,如果没超过,则该next[i]即为所求,跳出循环即可

可能会有人觉得这样求出来的会有重叠部分。

注意到我们枚举到后三分一的位置时,如果某个位置为i,

且next[i]+ i == len。

也就是子串的长度为next[i]了

由于对一个位置开始的子串的最大长度不能超过 (len – i)/2

那么很显然中间的那个串是不可能与后边的串有重叠的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 1111111
#define MAXM 211111
#define PI acos(-1.0)
#define eps 1e-8
#define INF 1e10
using namespace std;
int A[MAXN], B[MAXN];
char sa[MAXN];
void preExKmp(char x[],int m,int A[]){
    int ind=0,k=1;
    A[0]=m;
    while (ind + 1 < m && x[ind+1]==x[ind]) ++ind;
    A[1]=ind;
    for (int i=2;i<m;++i){
        if (i<=k+A[k]-1 && A[i-k]+i<k+A[k])
            A[i]=A[i-k];
        else{
            ind=max(0,k+A[k]-i);
            while (ind + i < m && x[ind+i]==x[ind]) ++ind;
            A[i]=ind,k=i;
        }
    }
}
void exKmp(char x[],int m , char y[],int n,int A[],int B[]){
    preExKmp(x,m,A);
    int ind=0,k=0;
    while (ind<n && ind<m && x[ind]==y[ind]) ind++;
    B[0]=ind;
    for (int i=1;i<n;++i){
        if (i < k+B[k]-1 && A[i-k]+i<k+B[k])
            B[i]=A[i-k];
        else{
            ind = max(0,k+B[k]-i);
            while (ind +i<n && ind<m && y[ind+i]==x[ind]) ++ind;
            B[i]=ind;k=i;
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", sa);
        int len = strlen(sa);
        preExKmp(sa, len, A);
        int ans = 0;
        int lst = len - len / 3, mxlen;
        for(int i = 0; i < len; i++)
        {
            mxlen = min(i, A[i]);
            mxlen = min(mxlen, (len - i) / 2);
            ans = max(ans, mxlen);
        }
        int res = 0;
        for(int i = lst; i < len; i++)
        {
            if(A[i] + i != len) continue;
            if(ans >= A[i])
            {
                res = A[i];
                break;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

参考:http://blog.csdn.net/sdj222555/article/details/14000929