poj2306,

## Problem:

Power Strings
 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 15878 Accepted: 6671
Description
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
Input
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
Output
For each s you should print the largest n such that s = a^n for some string a.
Sample Input
```abcd
aaaa
ababab
.```
Sample Output
```1
4
3```
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
Source
Waterloo local 2002.07.01

## Solution:

KMP; Just like POJ 1961.

## Source Code:

//Sat Apr 17 16:31:10 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

void kmp(string &str, vector<int> &data)
{
int i = 0;
int j = -1;
data = -1;
while (i < (int) str.size())
{
if (j == -1 || str[i] == str[j])
{
i++;
j++;
data[i] = j;
}
else
{
j = data[j];
}
}
return;
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
char s;
while (scanf("%s", s))
{
string str = s;
if (str == ".")
break;
int N = str.size();

vector<int> next(N + 1, 0);
kmp(str, next);
if (N % (N - next[N]) == 0)
cout << N / (N - next[N]) << endl;
else
cout << 1 << endl;
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}