﻿ • 价格透明
• 信息保密
• 进度掌控
• 售后无忧 # 专题训练一：字符串

#acm 专题训练一：字符串
##求最小循环节（next 数组）
kmp算法的一种 学习路径b站 添加链接描述

next数组

``````void getnex(char *s,int nex[])
{
int len = strlen(s);
int i = 0,j = -1;
nex = -1;
while(i < len)
{
if(j == -1 || s[i] == s[j])
{
i++;
j++;
nex[i] = j;
}
else
j = nex[j];
}
}

``````

A—Power Strings
Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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

``````#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include <typeinfo>
#define ll long long
#define MAXS 30
const int N=5*1e5+10;
using namespace std;

char s;
int ne;

void getnext(char *a)
{
int len = strlen(a);
int i = 0, j = -1;
ne = -1;
while(i < len)
{
if(j == -1 || a[i] == a[j])
{
ne[++i] = ++j;
}
else j = ne[j];
}
}
int main ()
{
while(scanf("%s",s) && s != '.')
{
getnext(s);
int l=strlen(s);
//		cout << l << endl;
//		for(int i=0; i<l ;i++ )
//		{
//			cout << ne[i] << " " ;
//		}
//		cout << endl;
//		cout << ne[l] << endl;

if(l % (l - ne[l]) ==0)
printf("%d\n",l/(l-ne[l]));
else
printf("1\n");
}
return 0;
}
`````` ### 低价透明 ### 金牌服务 ### 信息保密 