Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这题理论上是有问题的吧

Posted by fuheidog at 2018-04-18 16:25:17 on Problem 2752
In Reply To:这题理论上是有问题的吧 Posted by:philipyexushen at 2016-02-04 17:27:32
> #include <iostream>
> #include <algorithm>
> #include <functional>
> #include <string.h>
> 
> using namespace std;
> 
> static char str[400010];
> static int _Next[400010], store[400010];
> 
> void Get_Next(const int);
> 
> int main(void)
> {
> 	int Length, store_len;
> 	while (~scanf("%s", str))
> 	{
> 		Length = strlen(str);
> 		Get_Next(Length);
> 		store_len = 0;
> 
> 		//if (_Next[Length] >= Length / 2)
> 		//	store[store_len++] = Length;
> 		store[store_len++] = Length;
> 		for (int k = _Next[Length]; k > 0; k = _Next[k])
> 			store[store_len++] = k;
> 		for (int i = store_len - 1; i >= 0; i--)
> 			printf("%d ", store[i]);
> 		printf("\n");
> 	}
> 	return EXIT_SUCCESS;
> }
> 
> void Get_Next(const int Length)
> {
> 	int i = 0, k = -1;
> 	_Next[0] = -1;
> 
> 	while (i < Length)
> 	{
> 		if (k == -1 || str[i] == str[k])
> 		{
> 			i++;
> 			k++;
> 			_Next[i] = k;
> 		}
> 		else k = _Next[k];
> 	}
> }
> 
> 把if (_Next[Length] >= Length / 2)去掉就AC了
> 可是事实上如果去掉这个,abcaab就会输出2,6而事实上abcaab是不合法的吧


ab abcaab
合法

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator