C++编程10.12 Theme section(kmp算法)

2014/10/17 23:31
阅读数 84
Problem Description
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?
 

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.
 

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.
 
就是头上一个相同的,尾部一个相同的,中间还有一个相同的。阅读英语真是累人。。
不过还是多少学了点东西= =
 
shall be的用法。。前几天刚刚讲了kmp。。课上没怎么听懂,自己写了写好歹过了。庆祝。
 
#include<iostream>
#include<stdio.h>
#include<cstring>

#define NUM 1000000
using namespace std;

struct song
{
    char word[NUM];
    int length;
};

int main()
{
    int N;
    cin>>N;
    song *p =new song[N];
    for(int i=0; i<N; i++)
        //    gets(p[i].word);该函数可能读取最开始的= =输入输出流的东西还是不够熟悉= =
    {
		cin>>p[i].word;
		if(getchar()=='\n')
		{
			int l=0;
			for(int j=0;p[i].word[j]!='\0';j++)
				l++;
			p[i].length = l;//获取长度
		}
        
    }
    //cout<<p[0].length<<endl;//查看length
	//cout<<p[1].length<<endl;//查看length
	//cout<<p[2].length<<endl;//查看length
	//cout<<p[3].length<<endl;//查看length
	//cout<<p[4].length<<endl;//查看length
	//cout<<endl;
    for(int j=0; j<N; j++)//控制当前song
    {
        int max = 0;
        int num = 0;
        bool cyclength = true;
        for(int i=1; i<=p[j].length/3; i++)//循环E的长度
        {
            bool current = true;
            //if(!cyclength)//这是错误的,不需要。出现bababa这种情况,可能不是从正倒数第一个就开始相等。
               // break;
            for(int s=0; s<i; s++)//查看头尾字符是否相等
            {
                if(p[j].word[s]!=p[j].word[p[j].length-i+s])
                {
                    current = false;
                   // cyclength = false;
                    break;
                }
            }
            if(current)//从中间查找相同字符
            {
				num = i;
                int *str = new int[i];
                str[0] = 0;
                for(int q=0; q<i; q++)//next置数
                {
                    for(int w=0; w<q; w++)
                    {
                        bool count = true;
                        if(w+q>=i)
                            break;
                        if(p[j].word[w]==p[j].word[w+q])
                        {
                            str[q] = w;
                            count = false;
                        }
                        else
                        {
                            if(count)
                                str[q]=0;
                            break;
                        }
                    }
                }
                current = false;
                int c=i;
                int m=0;
                while(c<p[j].length-i)//kmp查找
                {
                    bool changec = false;
					
                    if(p[j].word[m]==p[j].word[c])
                    {
                        m++;
                        changec= true;
                    }
                    else
                        m = str[m];
                    if(m==i)
					{
						current = true;
						break;
					}
                    if(m==0||changec)
                        c++;
                }
            }
            if(current)//查找到字符
            {
                if(max>num)
                    continue;
                else
                    max = num;
            }
        }
        cout<<max<<endl;
    }
    delete p;
    return 0;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部