C++14(g++5.4) 解法, 执行用时: 383ms, 内存消耗: 5492K, 提交时间: 2019-12-08 20:44:49

#include <bits/stdc++.h>
using namespace std;

int main() {
  string S;
  while (cin >> S && S != ".") {
    S.push_back('#');
    int N = S.size();
    vector<int> next(N, -1);
    for (int i = 1; i < N; i++) {
      int j = next[i-1];
      while (j != -1 && S[i - 1] != S[j]) j = next[j];
      next[i] = j + 1;
    }
    int t = next[N-1];
    while (t != -1 && (N-1)%(N-1-t)) t = next[t];
    cout << (N-1) / (N-1-t) << endl;
  }
}

C++(g++ 7.5.0) 解法, 执行用时: 140ms, 内存消耗: 5232K, 提交时间: 2023-05-19 21:54:41

#include <bits/stdc++.h>
using namespace std ;
const int N=1e6+1;
char a[N];
int n,b[N];

void init()
{
    int i,j=0;

    for(i=1; i<n; i++)
    {
        while(j>0&&a[i+1]!=a[j+1]) j=b[j];
        if(a[i+1]==a[j+1]) j++;

        b[i+1]=j;
    }
}
int main()
{
    while(cin>>a+1,a[1]!='.')
    {
        n=strlen(a+1);
        init();
        if(n%(n-b[n])) cout<<1<<endl;
        else  cout<<n/(n-b[n])<<endl;
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 264ms, 内存消耗: 5588K, 提交时间: 2020-03-05 13:16:08

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string S;
	while(cin>>S&&S!=".")
	{
		S.push_back('#');
		int N=S.size();
		vector<int> next(N,-1);
		for(int i=1;i<N;i++)
		{
			int j=next[i-1];
			while(j!=-1&&S[i-1]!=S[j]) j=next[j];
			next[i]=j+1;
		}
		int t=next[N-1];
		while(t!=-1&&(N-1)%(N-1-t)) t=next[t];
		cout<<(N-1)/(N-1-t)<<endl;
	}
}