FilesExpand file tree

 master

/

2752.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (51 loc) · 969 Bytes

 master

/

2752.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (51 loc) · 969 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

#include <iostream>

#include <string>

using namespace std;

const int MAXN = 500000;

string T;

int failure[MAXN];

bool mark[MAXN];

void work(){

memset(mark,0,sizeof(mark));

failure[0] = failure[1] = 0;

int M = T.length();

for(int i=2; i<=M; i++){

int j = failure[i-1];

for(;;){

if(T[i-1]==T[j]){

failure[i] = j+1;

break;

}

if(j==0){

failure[i] = 0;

break;

}

j = failure[j];

}

}

/*

cout<<"print failure"<<endl;

for(int i=0; i<=M; i++){

cout<<failure[i]<<" ";

}

cout<<endl;

*/

int t = M;

while(1){

if(t == 0)break;

mark[t] = 1;

t = failure[t];

}

for(int i=1; i<M; i++){

if(mark[i]){

cout<<i<<" ";

}

}

cout<<M<<endl;

}

int main(){

while(cin>>T){

work();

}

return 0;

}