(简单) POJ 2406 Power Strings,扩展KMP。

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).

  水题,扩展KMP。

代码如下:

// ━━━━━━神兽出没━━━━━━
// ┏┓ ┏┓
// ┏┛┻━━━━━━━┛┻┓
// ┃ ┃
// ┃ ━ ┃
// ████━████ ┃
// ┃ ┃
// ┃ ┻ ┃
// ┃ ┃
// ┗━┓ ┏━┛
// ┃ ┃
// ┃ ┃
// ┃ ┗━━━┓
// ┃ ┣┓
// ┃ ┏┛
// ┗┓┓┏━━━━━┳┓┏┛
// ┃┫┫ ┃┫┫
// ┗┻┛ ┗┻┛
//
// ━━━━━━感觉萌萌哒━━━━━━ // Author : WhyWhy
// Created Time : 2015年07月18日 星期六 10时54分33秒
// File Name : 2406.cpp #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h> using namespace std; const int MaxN=; void EKMP_pre(int m,char s[],int next1[])
{
int p=,a=,L; next1[]=m; while(p+<m && s[p]==s[p+])
++p; next1[]=p; for(int k=;k<m;++k)
{
L=next1[k-a];
p=next1[a]+a-(next1[a]!=); if(k+L-<p)
next1[k]=L;
else
{
++p; while(p<m && s[p]==s[p-k])
++p; next1[k]=p-k;
a=k;
}
} next1[m]=;
} int N;
char s[MaxN];
int next1[MaxN]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout); while(~scanf("%s",s))
{
if(s[]=='.' && s[]==)
break; N=strlen(s); EKMP_pre(N,s,next1); int i; for(i=;i<N;++i)
if(next1[i]+i==N && next1[i]%i==)
break; printf("%d\n",N/i);
} return ;
}
上一篇:系统的启动模式(启动级别)的改动---使用upstart启动机制的


下一篇:NPOI 2.0 教程