Pagini recente » Cod sursa (job #3197107) | Profil The_only_one | Cod sursa (job #2468251) | Rating Adrian VELICU (Zweistein) | Cod sursa (job #1963720)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define in "strmatch.in"
#define out "strmatch.out"
#define NMAX (2000000 + 7)
#define MOD 100007
#define MOD2 666013
#define pb push_back
#define phi 52
using namespace std;
int szeA, szeB, pw[NMAX], hashValue, Hash, sze, hashValue2, Hash2, pw2[NMAX];
char A[NMAX], B[NMAX];
vector <int> sol;
int val(char ch) // OK
{
if(ch == 0) return 0;
if(ch <= 'z' && ch >= 'a') return (ch-'a');
return (26 + ch - 'A');
}
int main()
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
scanf("%s\n%s\n", A+1, B+1);
szeA = strlen(A+1);
szeB = strlen(B+1);
pw[0] = 1;
for(int i = 1; i<= szeA; ++i) pw[i] = (pw[i-1] * phi)%MOD;
pw2[0] = 1;
for(int i = 1; i<= szeA; ++i) pw2[i] = (pw2[i-1] * phi)%MOD2;
for(int i = 1; i<= szeA; ++i) hashValue = (hashValue*phi + val(A[i]))%MOD;
for(int i = 1; i<= szeA; ++i) hashValue2 = (hashValue2*phi + val(A[i]))%MOD2;
for(int i = 1; i<= szeB; ++i)
{
if(i >= szeA)
{
Hash = (Hash - (val(B[i-szeA]) * pw[szeA-1]) % MOD + MOD)%MOD;
Hash2 = (Hash2 - (val(B[i-szeA]) * pw2[szeA-1]) % MOD2 + MOD2)%MOD2;
}
Hash = (Hash * phi + val(B[i]))%MOD;
Hash2 = (Hash2 * phi + val(B[i]))%MOD2;
if(i >= szeA)
{
if(Hash == hashValue && Hash2 == hashValue2)
{
sol.pb(i-szeA);
}
}
}
sze = sol.size();
printf("%d\n", sze);
for(int i = 0; i< min(1000, sze); ++i) printf("%d ", sol[i]);
printf("\n");
return 0;
}