这次的题目多的有点变态啊！
我才做了8个模版体- -#，这几天慢慢补上去、
所谓的next数组： next[n] 表示从字符串前n个字符的前缀后缀的共有长度。
A - Number Sequence
Description
If there are more than one K exist, output the smallest one.
Input
a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].
Output
Sample Input
2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1
Sample Output
6 -1
返回匹配到的第一个字母的位置。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define N 1000010
#define M 10010
int next[N];
int S[N],p[M]; // S是主串，p是模式串
int a, b;
void get_next()
{
int i = 0,j = -1;
next[0] = -1;
int len = b;
while(i < len)
{
if(j == -1 || p[i] == p[j])
{
i ++;
j ++;
next[i] = j;
}
else
j = next[j];
}
}
int KMP()
{
get_next();
int i = 0, j = 0;
int len = a;
int m = b;
while(i < len && j < m)
{
if(j == -1 || S[i] == p[j])
{
i++;
j++;
}
else
j = next[j];
if(j == m)
{
return i - m + 1; //若匹配到，直接返回可以匹配的字符的位置。
}
}
return -1; // 若不匹配，返回 -1。
}
int main()
{
int n;
while(~scanf("%d",&n))
{
while(n --)
{
scanf("%d%d",&a,&b);
for(int i = 0; i < a; i ++)
{
scanf("%d",&S[i]);
}
for(int i = 0; i < b; i ++)
{
scanf("%d",&p[i]);
}
printf("%d\n",KMP());
}
}
return 0;
}
B - Oulipo
Description
Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination,
l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…
Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that
counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T's is not unusual. And they never use spaces.
So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All
the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.
Input
One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000.
Output
Sample Input
3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN
Sample Output
1 3 0
计算模式串在主串中出现过几次，代码中用count 计数，当匹配时，自加一，也就是输出的答案。
#include<stdio.h>
#include<string.h>
int next[1000010];
char S[1000010],p[10010];
void get_next()
{
int i=0,j=-1;
next[0]=-1;
int len=strlen(p);
while(i<len)
{
if(j==-1 || p[i]==p[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int KMP()
{
get_next();
int i=0,j=0,count=0;
int len=strlen(S);
int m=strlen(p);
while(i<len && j<m)
{
if(j==-1 || S[i]==p[j])
{
i++;
j++;
}
else
j=next[j];
if(j==m)
{
count++;
j=next[j];
}
}
return count;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
while(n --)
{
scanf("%s%s",p,S);
printf("%d\n",KMP());
}
}
return 0;
}
C - 剪花布条
Description
Input
Output
Sample Input
abcde a3 aaaaaa aa #
Sample Output
0 3
这题和B类似，但有不同的地方，匹配完需要重置。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define N 1010
int next[N];
char S[N],p[N]; // S是主串，p是模式串
void get_next()
{
int i = 0,j = -1;
next[0] = -1;
int len = strlen(p);
while(i < len)
{
if(j == -1 || p[i] == p[j])
{
i ++;
j ++;
next[i] = j;
}
else
j = next[j];
}
}
int KMP()
{
get_next();
int i = 0, j = 0, count = 0;
int len = strlen(S);
int m = strlen(p);
while(i < len && j < m)
{
if(j == -1 || S[i] == p[j])
{
i++;
j++;
}
else
j = next[j];
if(j == m)
{
count ++;
j = 0; //重置的地方
}
}
return count;
}
int main()
{
int n;
while(~scanf("%s",S))
{
if(S[0] == '#')
break;
scanf("%s",p);
printf("%d\n",KMP());
}
return 0;
}
D - Cyclic Nacklace
Description
inspired by the entrepreneurial spirit of "HDU CakeMan", he wants to sell some little things to make money. Of course, this is not an easy task.
As Christmas is around the corner, Boys are busy in choosing christmas presents to send to their girlfriends. It is believed that chain bracelet is a good choice. However, Things are not always so simple, as is known to everyone, girl's fond of the colorful
decoration to make bracelet appears vivid and lively, meanwhile they want to display their mature side as college students. after CC understands the girls demands, he intends to sell the chain bracelet called CharmBracelet. The CharmBracelet is made up with
colorful pearls to show girls' lively, and the most important thing is that it must be connected by a cyclic chain which means the color of pearls are cyclic connected from the left to right. And the cyclic count must be more than one. If you connect the leftmost
pearl and the rightmost pearl of such chain, you can make a CharmBracelet. Just like the pictrue below, this CharmBracelet's cycle is 9 and its cyclic count is 2:
Now CC has brought in some ordinary bracelet chains, he wants to buy minimum number of pearls to make CharmBracelets so that he can save more money. but when remaking the bracelet, he can only add color pearls to the left end and right end of the chain, that
is to say, adding to the middle is forbidden.
CC is satisfied with his ideas and ask you for help.
Input
Each test case contains only one line describe the original ordinary chain to be remade. Each character in the string stands for one pearl and there are 26 kinds of pearls being described by 'a' ~'z' characters. The length of the string Len: ( 3 <= Len <= 100000
).
Output
Sample Input
3 aaa abca abcde
Sample Output
0 2 5
求出最小环，然后再看需要加几个字符，使得题目中给出的串是循环的。
容易得出最小环 = len - next[len]。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define N 100010
int next[N];
char S[N],p[N]; // S是主串，p是模式串
void get_next()
{
int i = 0,j = -1;
next[0] = -1;
int len = strlen(p);
while(i < len)
{
if(j == -1 || p[i] == p[j])
{
i ++;
j ++;
next[i] = j;
}
else
j = next[j];
}
}
int KMP()
{
get_next();
int i = 0, j = 0, count = 0;
int len = strlen(S);
int m = strlen(p);
while(i < len && j < m)
{
if(j == -1 || S[i] == p[j])
{
i++;
j++;
}
else
j = next[j];
if(j == m)
{
count ++;
j = 0;
}
}
return count;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
while(n --)
{
scanf("%s",p);
int len = strlen(p);
get_next();
int whi = len - next[len];
//printf("%d\n",whi);
if(whi == len) // 这里易出错，容易忽略，和下面的判断条件混起来
printf("%d\n",len);
else if(len % whi == 0)
printf("0\n");
else
printf("%d\n",whi - len%whi);
}
}
return 0;
}
F - The Minimum Length
Description
shortest possible string A. For example, A="abcdefg". I got abcd efgabcdefgabcdefgabcdefg.... Then I cut the red part: efgabcdefgabcde as string B. From B, you should find out the shortest A.
Input
Output
Sample Input
bcabcab efgabcdefgabcde
Sample Output
3 7
D 会做，这题也就一定会做了，比D 还少了一步
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define N 1000010
int next[N];
char S[N],p[N]; // S是主串，p是模式串
void get_next()
{
int i = 0,j = -1;
next[0] = -1;
int len = strlen(p);
while(i < len)
{
if(j == -1 || p[i] == p[j])
{
i ++;
j ++;
next[i] = j;
}
else
j = next[j];
}
}
int KMP()
{
get_next();
int i = 0, j = 0, count = 0;
int len = strlen(S);
int m = strlen(p);
while(i < len && j < m)
{
if(j == -1 || S[i] == p[j])
{
i++;
j++;
}
else
j = next[j];
if(j == m)
{
count ++;
j = 0;
}
}
return count;
}
int main()
{
int n;
while(~scanf("%s",p))
{
int len = strlen(p);
get_next();
int whi = len - next[len];
printf("%d\n",whi);
}
return 0;
}
H - Seek the Name, Seek the Fame
Description
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
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Output
Sample Input
ababcababababcabab aaaaa
Sample Output
2 4 9 18 1 2 3 4 5
本题其实就是考察对next数组的理解吧。我用的是ans数组来存答案。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define N 400010
int next[N];
int ans[N];
char S[N],p[N]; // S是主串，p是模式串
void get_next()
{
int i = 0,j = -1;
next[0] = -1;
int len = strlen(p);
while(i < len)
{
if(j == -1 || p[i] == p[j])
{
i ++;
j ++;
next[i] = j;
}
else
j = next[j];
}
}
int KMP()
{
get_next();
int i = 0, j = 0, count = 0;
int len = strlen(S);
int m = strlen(p);
while(i < len && j < m)
{
if(j == -1 || S[i] == p[j])
{
i++;
j++;
}
else
j = next[j];
if(j == m)
{
count ++;
j = 0;
}
}
return count;
}
int main()
{
int n;
while(~scanf("%s",p))
{
int len = strlen(p);
int tmp_1 = len;
get_next();
int cnt = 0;
while(next[len])
{
len = next[len];
ans[cnt ++] = len;
}
if(ans[cnt - 1] != 0)
printf("%d ",ans[cnt - 1]);
for(int i = cnt - 2 ; i >= 0; i --)
{
printf("%d ",ans[i]);
}
printf("%d \n", tmp_1); // 一开始这里PE了一发，最后这样输出还是第一次见
}
return 0;
}
J - Simpsons’ Hidden Talents
Description
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
Output
The lengths of s1 and s2 will be at most 50000.
Sample Input
clinton homer riemann marjorie
Sample Output
0 rie 3
给出两个字符串，求第一个字符串的前缀和第二个 字符串的后缀的最大可能相同的长度，并且输出相同部分
如果把两个字符串连接起来，就直接变成next 数组的用法了，连接的时候，调用strcat函数，需要注意的是，当连接起来之后，next[len] 有可能大于两个字符串的长度，所以你要继续求next。
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAX 50010
char str1[MAX << 1];
char str2[MAX];
int next[MAX << 1];
void get_next(char *p)
{
int i = 0,j = -1;
next[0] = -1;
int len = strlen(p);
while(i < len)
{
if(j == -1 || p[i] == p[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
int main()
{
int n, m;
while(~scanf("%s%s",str1, str2))
{
int len1 = strlen(str1);
int len2 = strlen(str2);
strcat(str1, str2);
get_next(str1);
int len = len1 + len2;
while(next[len] > len1 || next[len] > len2) // 着重理解一下
len = next[len];
if(next[len])
{
for(int i = 0; i < next[len]; i ++)
printf("%c",str1[i]);
printf(" %d\n",next[len]);
}
else
printf("0\n");
}
return 0;
}
X - 最长回文
Description
回文就是正反读都是一样的字符串,如aba, abba等
Input
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
Output
Sample Input
aaaa abab
Sample Output
4 3
manacher 的模版体，具体可以参见http://blog.csdn.net/xi__long/article/details/43939067
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#define N 110010
char str[N];
char stc[N << 1];
int slen[N << 1];
void init(char *st, int len)
{
stc[0] = '@';
for(int i = 1; i <= 2*len; i += 2)
{
stc[i] = '#';
stc[i + 1] = str[i/2];
}
stc[2*len + 1] = '#';
stc[2*len + 2] = '$';
stc[2*len + 3] = 0;
}
int manacher(char *st, int len)
{
int mx = 0, ans = 0, po = 0;
for(int i = 1; i <= len; i ++)
{
if(mx > i)
slen[i] = min(mx - i, slen[2*po - i]);
else
slen[i] = 1;
while(stc[i - slen[i]] == stc[i + slen[i]])
slen[i] ++;
if(slen[i] + i > mx)
{
mx = slen[i] + i;
po = i;
}
ans = max(ans, slen[i]);
}
return ans - 1;
}
int main()
{
while(~scanf("%s",str))
{
int lenth = strlen(str);
init(str, lenth);
printf("%d\n",manacher(stc, lenth * 2 + 1));
}
}