Broken String

NC15536. Broken String

描述

Aguin has two strings A with the length of n and B with the length of m only contains lowercase letters.
But the strings are such antiques that some characters can’t be recognized (replaced with ’*’), and it can be any lowercase letters.
Now Aguin is wondering whether A is a substring of B. However, his way of match is a little strange. The detailed rules for match are as follows : the beginning of the A is aligned with the i^tℎcharacter of the B, and every character in the A can find the same one in B, and the position deviation does not exceed the k, then it is considered that A is matched with B in the subordinate position of the B. That is to say, for all j(1 ≤ j ≤ |A|), there is a p(1 ≤ P ≤ |B|), which the | j−(p−i+1) |≤k, i+j≤m and A[j] = B[p] all valid.

And if k=0, string ”***” can be matched with any other strings which length is 3.
Given strings A, B and the number k, you are supposed to find how many locations can A be matched in B.

输入描述

The first line contains an integer number T, the number of test cases.
For each test case :
The first line contains three integers n,m(1 ≤ n ≤ m ≤ 10⁵),k(1 ≤ k ≤ 10⁵), length of A, B and the number of deviation.
The second line contains a string A with the length of n.
The third line contains a string B with the length of m.
It is guaranteed that the strings contains only lowercase letters and ’*’.

输出描述

For each test case print the number of locations can S be matched in T.

示例1

输入:

4
3 5 1
abc
aabbc
3 5 1
a**
aabbc
3 5 1
abc
a*b*c
3 5 1
a*a
aabbb

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 36ms, 内存消耗: 11392K, 提交时间: 2018-04-24 11:14:03

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M =27;
bitset<N> pos[M],ans;

int cal(char c){
	if(c=='*') return 26;
	return c-'a';
}
int n,m,k,ext[N][M];
char s[N],t[N];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&m,&n,&k);
		scanf("%s%s",t,s);
		memset(ext,0,sizeof(ext));
		for(int i=0;i<M;i++) pos[i].reset();
		for(int i=0;i<n;i++){
			
			ext[max(i-k,0)][cal(s[i])]+=1;
			ext[min(i+k,n-1)+1][cal(s[i])]+=-1;
		}
		for(int i=0;i<n;i++){
			pos[26].set(i);
			for(int j=26;j>=0;j--){
				if(i) ext[i][j]+=ext[i-1][j];
				if(ext[i][j]>0||ext[i][26]>0) {
					pos[j].set(i);
				}
				
			}
		}
		ans=pos[cal(t[0])];
		for(int i=1;i<m;i++){
			ans<<=1;
			ans&=pos[cal(t[i])];
		}
		//for(int i=0;i<4;i++) cout<<pos[i]<<endl;
		printf("%d\n",ans.count());
	} 
	
	return 0;
}

上一题

下一题

详情