106 lines
3.5 KiB
C++
106 lines
3.5 KiB
C++
#include <algorithm>
|
|
#include <cassert>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <iostream>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
typedef unsigned long long ULL;
|
|
typedef long double LDB;
|
|
const int kMaxN = 1e6 + 10;
|
|
char S[kMaxN], T[kMaxN];
|
|
struct Block {
|
|
enum TypeT { wild, exact } type;
|
|
int L, R;
|
|
};
|
|
Block S_block[kMaxN], T_block[kMaxN];
|
|
int S_block_cnt, T_block_cnt;
|
|
int len_S, len_T;
|
|
ULL S_hash_data[kMaxN], T_hash_data[kMaxN], ksm[kMaxN];
|
|
void Process(char *S, int len_S, Block *blocks, int &block_cnt) {
|
|
int current_left_bound = 0;
|
|
Block::TypeT current_type =
|
|
(S[0] == '?' ? Block::TypeT::wild : Block::TypeT::exact);
|
|
for (int i = 1; i < len_S; i++) {
|
|
Block::TypeT this_type =
|
|
(S[i] == '?' ? Block::TypeT::wild : Block::TypeT::exact);
|
|
if (this_type == current_type) continue;
|
|
blocks[block_cnt++] = Block{current_type, current_left_bound, i - 1};
|
|
current_type = this_type;
|
|
current_left_bound = i;
|
|
}
|
|
blocks[block_cnt++] = Block{current_type, current_left_bound, len_S - 1};
|
|
}
|
|
void PrepareHash(char *src, int len, ULL *dst) {
|
|
static const ULL mul = 131;
|
|
dst[0] = src[0] - 'a' + 1;
|
|
for (int i = 1; i < len; i++) {
|
|
dst[i] = dst[i - 1] * mul;
|
|
dst[i] += src[i] - 'a' + 1;
|
|
}
|
|
}
|
|
ULL GetHsh(char *str, ULL *dat, int L, int R) {
|
|
ULL res = 0;
|
|
if (L > 0)
|
|
res = dat[R] - dat[L - 1] * ksm[R - L + 1];
|
|
else
|
|
res = dat[R];
|
|
return res;
|
|
}
|
|
bool Matched(int pos) {
|
|
int current_T_iterator = 0;
|
|
static int stored_begin_S_iterator = 0;
|
|
int current_S_iterator = stored_begin_S_iterator;
|
|
Block current_S_block = S_block[0];
|
|
Block current_T_block = T_block[0];
|
|
while (S_block[current_S_iterator].R < pos) current_S_iterator++;
|
|
stored_begin_S_iterator = current_S_iterator;
|
|
current_S_block = S_block[current_S_iterator];
|
|
assert(current_S_block.L <= pos);
|
|
assert(current_S_block.R >= pos);
|
|
current_S_block.L = pos;
|
|
while (true) {
|
|
int current_compare_length = min(current_S_block.R - current_S_block.L + 1,
|
|
current_T_block.R - current_T_block.L + 1);
|
|
if (current_S_block.type == Block::TypeT::exact &&
|
|
current_T_block.type == Block::TypeT::exact) {
|
|
if (GetHsh(S, S_hash_data, current_S_block.L,
|
|
current_S_block.L + current_compare_length - 1) !=
|
|
GetHsh(T, T_hash_data, current_T_block.L,
|
|
current_T_block.L + current_compare_length - 1))
|
|
return false;
|
|
}
|
|
if (current_compare_length == current_T_block.R - current_T_block.L + 1) {
|
|
if (current_T_iterator == T_block_cnt - 1) return true;
|
|
current_T_iterator++;
|
|
current_T_block = T_block[current_T_iterator];
|
|
} else
|
|
current_T_block.L += current_compare_length;
|
|
if (current_compare_length == current_S_block.R - current_S_block.L + 1) {
|
|
current_S_iterator++;
|
|
current_S_block = S_block[current_S_iterator];
|
|
} else
|
|
current_S_block.L += current_compare_length;
|
|
}
|
|
return true;
|
|
}
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
scanf("%s%s", S, T);
|
|
len_S = strlen(S);
|
|
len_T = strlen(T);
|
|
Process(S, len_S, S_block, S_block_cnt);
|
|
Process(T, len_T, T_block, T_block_cnt);
|
|
PrepareHash(S, len_S, S_hash_data);
|
|
PrepareHash(T, len_T, T_hash_data);
|
|
ksm[0] = 1;
|
|
static const ULL mul = 131;
|
|
for (int i = 1; i < kMaxN; i++) ksm[i] = ksm[i - 1] * mul;
|
|
for (int pos = 0; pos < len_S - len_T + 1; pos++) {
|
|
if (Matched(pos)) printf("%d\n", pos);
|
|
// fprintf(stderr, "pos=%d\n", pos);
|
|
}
|
|
return 0;
|
|
} |