KMP专题
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 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.
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 1000017
int ne[MAX];
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(){
char s[MAX];
while(scanf("%s",s)&&s[0]!='.'){
GetNext(s);
int len=strlen(s);
if(len%(len-ne[len])==0)printf("%d\n",len/(len-ne[len]));
else printf("1\n");
}
return 0;
} 示例代码
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
#define maxn 1000009
int nex[maxn];
char s[maxn*2], p[maxn];
void getnex(char p[]) {
int lenp = strlen(p);
int i = 0, j = -1;
nex[0] = -1;
while (i < lenp) {
if (j == -1 || p[i] == p[j]) {
i++; j++;
nex[i] = j;
}
else j = nex[j];
}
}
int main() {
//freopen("data.txt", "r", stdin);
while (scanf("%s", p) && p[0]!='.') {
getnex(p);
int len = strlen(p);
int mod = len - nex[len];
if (len % mod != 0) printf("1\n");
else printf("%d\n", len/mod);
}
//fclose(stdin);
return 0;
}B - Seek the Name, Seek the Fame
The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:
Step1. Connect the father's name and the mother's name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).
Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)
Input
The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Output
For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby's name.
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
我的代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;//为什么不加这行 sort就用不了
#define max 400000
int ne[max],num[max];
int len=0,p=0;//j为长度的个数
void GetNext(char *s){
int i=0,j=-1;
ne[0]=-1;
len=strlen(s);
//cout<<len<<endl;
while(i<len){
if(j==-1||s[i]==s[j]){
ne[++i]=++j;
// cout<<i<<" "<<j<<endl;
}
else j=ne[j];
}
}
void Search(int *ne,int pos){
if(ne[pos]==0)return ;
num[p++]=ne[pos];
// cout<<"pos is"<<ne[pos]<<endl;
Search(ne,ne[pos]);
}
int main(){
char s[max];
while(scanf("%s",s)!=EOF) {
p=0;
GetNext(s);
Search(ne,len);//为什么是len而不是len-1
num[p++]=len;
sort(num,num+p);
for(int i=0;i<p;i++){
printf("%d ",num[i]);
}
printf("\n");
}return 0;
}
示例代码
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
#define maxn 400009
int nex[maxn];
char str[maxn];
int ans[maxn], tot, len;
void getnex() {
int i = 0, j = -1;
nex[0] = -1;
while (i < len) {
if (j == -1 || str[i] == str[j]) {
i++; j++;
nex[i] = j;
}
else j = nex[j];
}
}
void getAns(){
tot = 0;
int pos = len;
while(pos) {
ans[tot++] = pos;
pos = nex[pos];
}
}
int main() {
//freopen("data.txt", "r", stdin);
while (scanf("%s", str) != EOF) {
len = strlen(str);
getnex();
getAns();
for (int i = tot - 1; i >= 0; --i) {
if (i) printf("%d ", ans[i]);
else printf("%d\n", ans[i]);
}
}
//fclose(stdin);
return 0;
}
C - Simpsons’ Hidden Talents
Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had.
Marge: Yeah, what is it?
Homer: Take me for example. I want to find out if I have a talent in politics, OK?
Marge: OK.
Homer: So I take some politician’s name, say Clinton, and try to find the length of the longest prefix
in Clinton’s name that is a suffix in my name. That’s how close I am to being a politician like Clinton
Marge: Why on earth choose the longest prefix that is a suffix???
Homer: Well, our talents are deeply hidden within ourselves, Marge.
Marge: So how close are you?
Homer: 0!
Marge: I’m not surprised.
Homer: But you know, you must have some real math talent hidden deep in you.
Marge: How come?
Homer: Riemann and Marjorie gives 3!!!
Marge: Who the heck is Riemann?
Homer: Never mind.
Write a program that, when given strings s1 and s2, finds the longest prefix of s1 that is a suffix of s2.
Input
Input consists of two lines. The first line contains s1 and the second line contains s2. You may assume all letters are in lowercase.
Output
Output consists of a single line that contains the longest string that is a prefix of s1 and a suffix of s2, followed by the length of that prefix. If the longest such string is the empty string, then the output should be 0.
The lengths of s1 and s2 will be at most 50000.
Sample Input
clinton
homer
riemann
marjorie
Sample Output
0
rie 3
我的代码,有问题显示越界
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define max 100000
int len1,len2,len;
int ne[50000];
void GetNext(char *s){
int i=len1,j=-1;
ne[0]=-1;
while(i<len&&j<len1){
if(j==-1||s[i]==s[j]){
ne[++i]=++j;
// cout<<i<<" "<<j<<endl;
}
else j=ne[j];
}
}
int main(){
char s1[50000],s2[50000];
while(scanf("%s",s1)!=EOF){
scanf("%s",s2);
len1=strlen(s1);
len2=strlen(s2);
/* for(int i=0;i<len1;i++){//将两个字符串合并在一起
s[i]=s1[i];
}*/
for(int i=len1,j=0;i<len1+len2;i++,j++){
s1[i]=s2[j];
}
len=len1+len2;
GetNext(s1);
//printf("%d",ne[len]);
if(ne[len]==-1)printf("0\n");
else {
for(int i=0;i<ne[len];i++){
printf("%c",s1[i]);
}
printf(" %d\n",ne[len]);
}
}
}示例代码
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
#define maxn 50009
int nex[maxn*2];
char str[maxn*2], t_str[maxn];
void getnex(char p[]) {
int lenp = strlen(p);
int i = 0, j = -1;
nex[0] = -1;
while (i < lenp) {
if (j == -1 || p[i] == p[j]) {
i++; j++;
nex[i] = j;
}
else j = nex[j];
}
}
int main() {
//freopen("data.txt", "r", stdin);
while (scanf("%s %s", str, t_str) != EOF) {
strcat(str,"$");
strcat(str, t_str);
getnex(str);
int len = strlen(str);
if (nex[len]) {
str[nex[len]] = '\0';
printf("%s %d\n", str, nex[len]);
} else {
printf("0\n");
}
}
//fclose(stdin);
return 0;
}
