Pagini recente » Cod sursa (job #1999157) | Cod sursa (job #1374206) | Cod sursa (job #971578) | Cod sursa (job #1607921) | Cod sursa (job #2777688)
#include <bits/stdc++.h>
#define DIM 2000005
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, hashA1, hashA2, hashB1, hashB2, nr;
int P1, P2;
char A[DIM], B[DIM];
vector <int> ans;
int main()
{
f >> A >> B;
int n = strlen(A);
int m = strlen(B);
P1 = P2 = 1;
for(int i = 0; i < n; i++)
{
hashA1 = (hashA1 * P + A[i]) % MOD1;
hashA2 = (hashA2 * P + A[i]) % MOD2;
if(i)
{
P1 = P1 * P % MOD1;
P2 = P2 * P % MOD2;
}
}
if(n > m)
{
g << 0 << "\n";
return 0;
}
for(int i = 0; i < n; i++)
{
hashB1 = (hashB1 * P + B[i]) % MOD1;
hashB2 = (hashB2 * P + B[i]) % MOD2;
}
if(hashA1 == hashB1 && hashA2 == hashB2)
ans.push_back(0), nr++;
for(int i = n; i < m; i++)
{
hashB1 = ((hashB1 + MOD1 - (B[i - n] * P1) % MOD1) * P % MOD1 + B[i]) % MOD1;
hashB2 = ((hashB2 + MOD2 - (B[i - n] * P2) % MOD2) * P % MOD2 + B[i]) % MOD2;
if(hashA1 == hashB1 && hashA2 == hashB2 && nr <= 1000)
ans.push_back(i - n + 1), nr++;
}
g << nr << "\n";
for(auto k : ans)
g << k << " ";
return 0;
}