KMP    发布于 2019-07-21   441人围观   0条评论

Description

Mr. 'Jotishi' is a superstitious man. Before doing anything he usually draws some strange figures, and decides what to do next.

One day he declared that the names that contain a string S as substring is unlucky. For example, let S be 'ab', then 'abc', 'cabe', 'pqqab', 'ab' etc are unlucky but 'ba', 'baa' etc are not.

So, he gives you the string S and asks you to find the number of names of length n, which are lucky, that means you have to find the number of strings that don't contain S as substring.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 109). The next line contains the allowed characters for a name. This non-empty line contains lowercase characters only and in ascending order. The next line contains a string S (1 ≤ length(S) ≤ 50), and S contains characters from the allowed characters only.

Output

For each case, print the case number and the total number of names that don't cont

查看更多
KMP    发布于 2019-07-21   400人围观   0条评论

Description

A string is said to be a palindrome if it remains same when read backwards. So, 'abba', 'madam' both are palindromes, but 'adam' is not.

Now you are given a non-empty string S, containing only lowercase English letters. The given string may or may not be palindrome. Your task is to make it a palindrome. But you are only allowed to add characters at the right side of the string. And of course you can add any character you want, but the resulting string has to be a palindrome, and the length of the palindrome should be as small as possible.

For example, the string is 'bababa'. You can make many palindromes including

bababababab

babababab

bababab

Since we want a palindrome with minimum length, the solution is 'bababab' cause its length is minimum.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing a string S. You can assume that 1 ≤ length(S) ≤ 106.

Output

For each case, print the case number and the length of the shorte

查看更多
KMP    发布于 2019-07-20   345人围观   0条评论

题目大意

求给定的字符串所有前缀在字符串中出现次数的总和mod10007的值

题解

这题的结论是这样的:求出next数组,然后从后向前,依次累加……

算了我也说不明白,还是给个代码合适。。。。

for(int i = 1;i <= n;++i){
	a[i] = 1;
}
for(int i = n;i >= 1;--i)
    a[nxt[i]] += a[i];

就是这样的一个结论,然后O(n)就能求出所有我们要的结果。

其中ai代表以当前位置i为结尾的前缀字符串在原字符串中出现的次数。

为什么这样可以做?
我个人的想法是……KMP中的next数组,实际上表示的真正含义为到位置pos为止的前缀字符串中,最长的能够匹配的前缀和后缀的长度(这里的前缀和后缀值得是我们取出的前缀字符串的前缀和后缀,而且这里的前缀和后缀的长度不能和取出的这个前缀字符串的长度相等)。

于是我们想,如果我们取出一个前缀,结束位置为pos,他出现过x次,那么他对应的以next[pos]为结尾的前缀字符串一定也会随着这个前缀串出现x+1次。但是这其中还有一次是会不断算重复的,于是累加的时候就加x,把本身有的那一次放入初始化的时候,先对每个位置的值赋值1。

其实我也不是很明白这样正确性怎么证明,但是毕竟icpc吗,要大胆猜想……

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
const int maxn = 2e5+5;
int cas;
char s[maxn];
int a[maxn];
int nxt[maxn];
void KMP(){
	int j = 0;
	nxt[1] = 0;
	int len = strlen(s+1);
	for(int i = 2;i <= len;++i){
		while(j && s[i] != s[j+1])j = nxt[j];
		if(s[j+1] == s[i])j++;
		nxt[i] = j;
	}
	return;
}
int T;
const int mod = 10007;
int main(){
	scanf("
查看更多
字符串 KMP    发布于 2019-04-05   350人围观   0条评论

 

 

不解释,就是KMP模板题……给出个人常用KMP模板QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s1;
string s2;
int n;
int cnt = 0;
const int maxn = 10005;
int nxt[maxn];
void KMP_pre(){
    int j = -1;
    nxt[0] = -1;
    for(int i = 1;i < s1.size();++i){
        while(j != -1 && s1[j+1] != s1[i])
            j = nxt[j];
        if(s1[j+1] == s1[i]){
            j++;
            nxt[i] = j;
        }
        else nxt[i] = -1;
    }
    return;
}
void KMP(){
    int j = -1; 
    cnt = 0;
    for(int i = 0;i < s2.size();++i){
        while(j != -1 && s1[j+1] != s2[i])
            j = nxt[j];
        if(s1[j+1] == s2[i])j++;
        if(j == s1.size()-1){
            cnt++;
            j = nxt[j];
        }
    }
    return;
}
int main(){
    cin >> n;
    while(n--){
        cin >> s1;
        cin >> s2;
        KMP_pre();
        KMP();
        cout << cnt << endl;
    }
    return 0;
}

 

查看更多