KMP–Cyclic Nacklace

 题目网址:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110060\#problem/D

题材网址: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110060\#problem/B

Description

Description

CC always becomes very depressed at the end of this month, he has
checked his credit card yesterday, without any surprise, there are only
99.9 yuan left. he is too distressed and thinking about how to tide over
the last days. Being inspired by the entrepreneurial spirit of “HDU
CakeMan”, he wants to sell some little things to make money. Of course,
this is not an easy task. 

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’. 

As Christmas is around the corner, Boys are busy in choosing christmas
presents to send to their girlfriends. It is believed that chain
bracelet is a good choice. However, Things are not always so simple, as
is known to everyone, girl’s fond of the colorful decoration to make
bracelet appears vivid and lively, meanwhile they want to display their
mature side as college students. after CC understands the girls demands,
he intends to sell the chain bracelet called CharmBracelet. The
CharmBracelet is made up with colorful pearls to show girls’ lively, and
the most important thing is that it must be connected by a cyclic chain
which means the color of pearls are cyclic connected from the left to
right. And the cyclic count must be more than one. If you connect the
leftmost pearl and the rightmost pearl of such chain, you can make a
CharmBracelet. Just like the pictrue below, this CharmBracelet’s cycle
is 9 and its cyclic count is 2: 

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? 

图片 1

 

Now CC has brought in some ordinary bracelet chains, he wants to buy
minimum number of pearls to make CharmBracelets so that he can save more
money. but when remaking the bracelet, he can only add color pearls to
the left end and right end of the chain, that is to say, adding to the
middle is forbidden. 
CC is satisfied with his ideas and ask you for help.

Input

 

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.

Input

 

The first line of the input is a single integer T ( 0 < T <= 100 )
which means the number of test cases. 
Each test case contains only one line describe the original ordinary
chain to be remade. Each character in the string stands for one pearl
and there are 26 kinds of pearls being described by ‘a’ ~’z’ characters.
The length of the string Len: ( 3 <= Len <= 100000 ).

Output

 

There will be N lines in the output, where the i-th line denotes the
maximum possible length of the theme section of the i-th song. 

Output

 

For each case, you are required to output the minimum count of pearls
added to make a CharmBracelet.

Sample Input

 

5 xy abc aaa aaaaba aaxoaaaaa

Sample Input

 

3

Sample Output

aaa

0 0 1 1 2

abca

 

abcde

题意:
输入一个字符串,求之字符串中之一个子串,该子串为这个字符串的前缀和后缀,并当字符串中间也时有发生之子串,但但眼看三单子串不可知重叠,求是否留存这么的子串,输出子串长的不过特别价值,否则输出0;

 

 

Sample Output

思路:
使用扩展KMP算法,扩展KMP的next[i]表示从s[i]开头的跟s前缀最深之匹配长度。在一个位置i中,如果一旦满足要求,子串的顶特别尺寸不能够跳

0

min(i,  next[i], (len – i) / 2)
,所有的绝可怜尺寸的太老价值就是可能有的极其深尺寸。先找找利用next[]摸中间与前面缀匹配的子串,然后判断后缀与子串匹配的无比可怜尺寸,并要注意子串不克重叠。

2

 

5

代码:

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
char s[1000005];
int nex[1000005];
int pre[1000005];

void ex_next(int length)
{
    ///nex[i]: 以第i位置开始的子串与T的前缀的最大长度;
    int i,j;
    nex[0]=length;
    for(i=0; i<length-1&&s[i]==s[i+1];i++);///前缀都是同一个字母的时候;
    nex[1]=i;
    int a=1;///a为使匹配到最远的地方时的起始匹配地点;
    for(int k=2;k<length;k++)
    {
        int p=a+nex[a]-1,L=nex[k-a];
        if( (k-1)+L>=p )
        {
            int j=(p-k+1)>0?(p-k+1):0;
            while(k+j<length&&s[k+j]==s[j]) j++;
            /// 枚举(p+1,length) 与(p-k+1,length) 区间比较;
            nex[k]=j,a=k;
        }
        else nex[k]=L;
    }
}

int main()
{
    int T,M,n;
    scanf("%d",&T);
    while(T--)
    {
        M=0;
        scanf("%s",s);
        int len=strlen(s);
        ex_next(len);
        for(int i=1;i<len;i++)
        {
            if(nex[i])
            {
                ///此时nex[i]为中间以s[i]开始的子串与前缀匹配的最大长度;
                ///接下来判断后缀与前缀及中间子串的最大匹配长度;
                n=min(min (i,nex[i]),(len-i)/2);
                for(int j=len-n;j<len;j++)
                  if(nex[j]==len-j)
                {
                    if(M<nex[j]) M=nex[j];
                    else         break;
                }
            }
        }
        printf("%d\n",M);
    }
    return 0;
 }

题意:输入一个字符串,在结尾或前端添加字符
,使字符串首个连续后做循环,字符串必须带有循环节,即至少含有2个循环节。

 

 

 

思路:在最后或前端添加字符
,使字符串首各连续后做循环,仔细分析后发现于前后添加字符的效益是同一的,故只当最后添加。考虑字符串abcabcab的next[]屡组值为0,0,0,1,2,3,4,5
 
next[7]=5为字符串尾部与眼前缀匹配的极致可怜长,s[0]=s[3],s[3]=s[6],s[0]=s[6],可以窥见在周期长呢3,所以于有所字符串min=len-next[len-1]啊极小周期。

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
char s[100005];
int  p[100005];

void next_(int len)
{
    int k=0;
    p[0]=0;
    for(int i=1;i<len;i++)
    {
        while(k>0&&s[k]!=s[i])
            k=p[k-1];
        if(s[k]==s[i])
            k++;
        p[i]=k;
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        int len=strlen(s);
        next_(len);
        int minn=len-p[len-1];
        if(minn==len) printf("%d\n",len);
        else  printf("%d\n",(minn-len%minn)%minn);
    }
    return 0;
}