您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

专题训练一:字符串

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

next数组

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

循环节有几位 next数组就有几个0

例题:
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[1000005];
int ne[1000005];

void getnext(char *a)
{
	int len = strlen(a);
	int i = 0, j = -1;
	ne[0] = -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[0] != '.')
	{
		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;
}

转载


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进