FilesExpand file tree

 master

/

10298.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

69 lines (52 loc) · 1011 Bytes

 master

/

10298.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

69 lines (52 loc) · 1011 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

59

60

61

62

63

64

65

66

67

68

#include <iostream>

#include <string.h>

#include <string>

#include <stdio.h>

using namespace std;

const int MAXN = 1000010;

const int INF = 99999999;

char S[MAXN];

int failure[MAXN];

void build_failure(){

memset(failure,0,sizeof(failure));

int M = strlen(S);

int j;

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

j = failure[i-1];

for(;;){

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

failure[i] = j+1;

break;

}

if(j==0){failure[i] = 0;break;}

j = failure[j];

}

}

/*

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

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

}cout<<endl;

*/

int tmp = INF;

if(M%(M-failure[M])==0){

tmp = min(M-failure[M], tmp);

}

int ans;

if(tmp==INF){

ans = 1;

}else{

ans = M/tmp;

}

cout<<ans<<endl;

}

void work(){

build_failure();

}

int main(){

while(1){

scanf("%s",S);

if(S[0]=='.')break;

work();

}

return 0;

}