bzoj4503: 两个串 bitset

---

目录

• [TOC]

题目链接

bzoj4503: 两个串

题解

暴一发bitset
f[i][j] 表示 S[1..i] 是否有个后缀能匹配 T[1..j]
那么假设 S[i+1] 能匹配 T[s]，令 f[i+1][s] | = f[i][s-1]
所以预处理理出每个字符能匹配 T的哪些位置,设为[c]
那么 f[i]=((f[i-1]<<1)|(1<<1)) & mat[S[i]]
直接在mat上做匹配就好了
时间复杂度：O(|S||T|/32)

代码

#include<cstdio>
#include<bitset> 
#include<cstring>
#include<algorithm>
#define LL long long
#define gc getchar()
#define pc putchar
#define LD long double
inline int read() {
    int x = 0,f = 1;
    char c = gc;
    while(c < '0' || c > '9' )c = gc;
    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;
    return x * f ;
}
void print(int x) { 
    if(x >= 10) print(x / 10); 
    pc(x % 10 + '0'); 
} 
const int maxn = 100007;  
char s[maxn],t[maxn]; 
std::bitset<maxn>mat[30],ans;  
int main() {  
    scanf("%s%s",s + 1,t + 1);  
    int n = strlen(s + 1),m = strlen(t + 1);  
    for(int i = 1;i <= n;++ i) mat[s[i] - 'a'].set(i);  
    ans.set();  
    for(int i = 1;i <= m;++ i)  
        if(t[i] != '?') ans &= (mat[t[i] - 'a'] >> (i - 1));  
    int cnt = 0;  
    for(int i = 1;i <= n - m + 1;++ i) if(ans[i] == 1) cnt ++;  
    print(cnt);   
    pc('
'); 
    for(int i = 1;i <= n - m + 1;++ i) if(ans[i] == 1)print(i - 1),pc('
');  
    return 0;  
}