Pagini recente » Cod sursa (job #2391461) | Cod sursa (job #2032532) | Cod sursa (job #2124413) | Cod sursa (job #264691) | Cod sursa (job #902763)
Cod sursa(job #902763)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
typedef vector<int>::iterator it;
const int oo = 0x3f3f3f3f;
const int MAX_N = 2000005;
const int MAX_MATCH = 1000;
const int MAX_U = 2;
const int U[] = {666013, 1000003};
const int Base = 67;
int N, M, MatchCount;
char Pattern[MAX_N], String[MAX_N];
vector<int> MatchPositions;
/*
int Pi[MAX_N];
int Z[MAX_N];
void BuildPi() {
Pi[1] = 0;
for (int i = 1, p = 0; i < N; ++i) {
for (; p > 0 && Pattern[i + 1] != Pattern[p + 1]; p = Pi[p]);
p += (Pattern[i + 1] == Pattern[p + 1] ? 1 : 0);
Pi[i + 1] = p;
}
}
void KMP() {
BuildPi();
for (int i = 1, p = 0; i <= M; ++i) {
for (; p > 0 && String[i] != Pattern[p + 1]; p = Pi[p]);
p += (String[i] == Pattern[p + 1] ? 1 : 0);
if (p == N) {
++MatchCount;
if (MatchCount <= MAX_MATCH)
MatchPositions.push_back(i - N + 1);
}
}
}
void BuildZ() {
int Right = 0, Position = 0;
for (int i = 2; i <= N; ++i) {
if (Right >= i)
Z[i] = min(Right - i + 1, Z[i - Position + 1]);
for (; i + Z[i] <= N && Pattern[Z[i] + 1] == Pattern[i + Z[i]]; ++Z[i]);
if (i + Z[i] - 1 > Right) {
Position = i;
Right = i + Z[i] - 1;
}
}
}
void ZAlgorithm() {
BuildZ();
int Right = 0, Position = 0;
for (int i = 1; i <= M; ++i) {
int LCP = 0;
if (Right >= i)
LCP = min(Right - i + 1, Z[i - Position + 1]);
for (; LCP < N && i + LCP <= M && Pattern[LCP + 1] == String[i + LCP]; ++LCP);
if (i + LCP - 1 > Right) {
Position = i;
Right = i + LCP - 1;
}
if (LCP == N) {
++MatchCount;
if (MatchCount <= MAX_MATCH)
MatchPositions.push_back(i);
}
}
}*/
inline bool Equal(int Key1[], int Key2[]) {
for (int i = 0; i < MAX_U; ++i)
if (Key1[i] != Key2[i])
return false;
return true;
}
inline int Digit(const char C) {
if ('a' <= C && C <= 'z')
return C - 'a' + 1;
if ('A' <= C && C <= 'Z')
return C - 'A' + 27;
if ('0' <= C && C <= '9')
return C - '0' + 53;
return 0;
}
void RabinKarp() {
int PatternHash[MAX_U] = {0, 0}, BasePow[MAX_U] = {1, 1};
for (int i = 1; i <= N; ++i) {
for (int h = 0; h < MAX_U; ++h) {
PatternHash[h] = (PatternHash[h] * Base + Digit(Pattern[i])) % U[h];
BasePow[h] = (BasePow[h] * Base) % U[h];
}
}
int Hash[MAX_U] = {0, 0};
for (int i = 1; i < N; ++i)
for (int h = 0; h < MAX_U; ++h)
Hash[h] = (Hash[h] * Base + Digit(String[i])) % U[h];
for (int i = N; i <= M; ++i) {
for (int h = 0; h < MAX_U; ++h) {
Hash[h] = (Hash[h] * Base + Digit(String[i])) % U[h];
Hash[h] = (Hash[h] - (BasePow[h] * Digit(String[i - N])) % U[h] + U[h]) % U[h];
}
if (Equal(PatternHash, Hash)) {
++MatchCount;
if (MatchCount <= MAX_MATCH)
MatchPositions.push_back(i - N + 1);
}
}
}
void Solve() {
//KMP();
//ZAlgorithm();
RabinKarp();
}
void Read() {
assert(freopen("strmatch.in", "r", stdin));
assert(scanf("%s\n%s", Pattern + 1, String + 1) == 2);
N = strlen(Pattern + 1);
M = strlen(String + 1);
}
void Print() {
assert(freopen("strmatch.out", "w", stdout));
printf("%d\n", MatchCount);
for (it P = MatchPositions.begin(); P != MatchPositions.end(); ++P)
printf("%d ", *P - 1);
printf("\n");
}
int main() {
Read();
Solve();
Print();
return 0;
}