Tag-KMP

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-07-21 20:34:56 |  0 Comments  |  KMP

Light OJ 1268 Unlucky Strings KMP DP矩阵快速幂优化

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

 2019-07-21 20:14:23 |  0 Comments  |  KMP

Light OJ 1258 Making Huge Palindromes KMP构造回文串

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

 2019-07-20 21:56:59 |  0 Comments  |  KMP

HDU 3336 Count the string KMP(瞎搞)

题目大意

求给定的字符串所有前缀在字符串中出现次数的总和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("
 2019-04-05 22:47:29 |  0 Comments  |  字符串 KMP

POJ3461Oulipo -KMP模板题

 

 

不解释,就是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;
}

 

Title - Artist
0:00