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

1次AC,思路想想就有了,见代码

Posted by hanzeil at 2014-08-15 20:11:59 on Problem 2752
#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
char s[400010];
int next_[400010];
void get_next(){
	next_[0] = -1;
	for (int i = 0, j = -1; s[i];){
		if (j == -1 || s[i] == s[j]){
			i++; j++;
			next_[i] = j;
		}
		else{
			j = next_[j];
		}
	}
}
int main(){
	while (cin >> s){
		stack<int> stk;
		//初始化
		memset(next_, 0, 400010 * sizeof(int));
		stk.push(strlen(s));
		get_next();
		int t = next_[strlen(s)];
		while (t){
			stk.push(t);
			t = next_[t];
		}
		while (!stk.empty()){
			cout << stk.top() << " ";
			stk.pop();
		}
		cout << endl;
	}
	return 0;
}

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