hd1711

Number Sequence

这篇排版有问题，不过试了几次都改不来也就这样吧

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 51840 Accepted Submission(s): 20751

Problem Description

Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M – 1] = b[M]. If there are more than one K exist, output the smallest one.

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

Sample Input

2

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2

1 2 3 1 3

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1

Sample Output

6

-1

做题思路：给出一个主序列，和一个匹配序列，如果能够匹配，则输出匹配序列第一个数在主序列中的位置.

这道题是kmp的基础题.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1000100], b[10004],NEXT[10010];
int t, x, y;
void getNETE() 
{
	int j=0,k=-1;
	NEXT[0] = -1;
	while(j<y-1)
	{
		if(k==-1 || b[j]==b[k])
		{
			j++;
			k++;
			NEXT[j] = k;
		}
		else	
		k = NEXT[k];
	}
}
void kmp()
{
	int i=0,j=0;
	while(i<x&&j<y)
	{
		if(j==-1 || a[i]==b[j]) 
		{
			i++;
			j++;
		} 
		else
		j = NEXT[j];
	}
	if(j==y)
		cout<<i-y+1<<endl;//返回下标
	else
		 cout<<-1<<endl;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&x,&y);
		for(int p=0;p<x;p++)
		{
			scanf("%d",&a[p]);
		}
		for(int p=0;p<y;p++)
		{	
			scanf("%d",&b[p]);
		}
		getNETE();
		kmp();
	}
	return 0;
}

开始输入啥都没问题，然后就是通不过，说什么时间超限，最后改过了改过去，才发现，用的是cin输入输出流，这个在算法竞赛那本紫书中也提到了，以后注意，然后尽量改掉用万能有文件的习惯，有的编译器，不支持。

Cyclic Nacklace
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7375    Accepted Submission(s): 3210

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

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:

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 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
For each case, you are required to output the minimum count of pearls added to make a CharmBracelet.
 

Sample Input
3 aaa abca abcde
 

Sample Output
0 2 5

[题目大意：求再加几个，才能构成循环] 

【题解】【kmp】

【kmp,利用失配函数，求出最小循环节（最小循环节=原串长度-末位失配），首先判断循环节是否为0，若为0，直接输出原串长度；然后看原串是否能被循环节整除，若能，则输出0,；若不能，则求出还有几位没有循环，输出】

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100010;
char str[MAXN];
int _next[MAXN];

void getNext(char *p)
{
    int j,k;
    j=0;
    k=-1;
    int len=strlen(p);
    _next[0]=-1;
    while(j<len)
    {
        if(k==-1||p[j]==p[k])
        {
            j++;
            k++;
            _next[j]=k;
        }
        else k=_next[k];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",&str);
        getNext(str);
        int len=strlen(str);//str字符串的个数 
        if(_next[len]==0)// 判断循环节是否为0，若为0，直接输出原串长度；
        {
            printf("%d\n",len);
            continue;
        }
        int t=len-_next[len];
        if(len%t==0)//原串是否能被循环节整除
		printf("0\n");
        else
        {
            printf("%d\n",t-len%t);//几位没有循环
        }
    }
    return 0;
}