Pagini recente » Cod sursa (job #69228) | Cod sursa (job #2119675) | Cod sursa (job #1873749) | Cod sursa (job #1160416) | Cod sursa (job #2905942)
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000003
#define MOD2 1000007
#define baza 123
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector < ll > rasp;
ll h1, h2, H1, H2, P1, P2;
char sir1[2000005], sir2[2000005];
int main()
{
ll x, y, i;
fin.getline(sir1, 2000005);
fin.getline(sir2, 2000005);
h1 = 0, H1 = 0, h2 = 0, H2 = 0, P1 = P2 = 1;
x = strlen(sir1), y = strlen(sir2);
for(i = 0; i < x; i++)
{
h1 = (h1 * baza + sir1[i]) % MOD;
H1 = (H1 * baza + sir1[i]) % MOD2;
}
for(i = 0; i < x; i++)
{
h2 = (h2 * baza + sir2[i]) % MOD;
H2 = (H2 * baza + sir2[i]) % MOD2;
if(i != 0) P1 = (P1 * baza) % MOD, P2 = (P2 * baza) % MOD2;
}
if(h1 == h2 && H1 == H2) rasp.push_back(0);
for(i = x; i < y; i++)
{
h2=((h2-(sir2[i-x]*P1)%MOD+MOD)*baza+sir2[i])%MOD;
H2=((H2-(sir2[i-x]*P2)%MOD2+MOD2)*baza+sir2[i])%MOD2;
if(h1 == h2 && H1 == H2) rasp.push_back(i-x+1);
}
fout << rasp.size() << '\n';
for(int i:rasp) fout << i << ' ';
return 0;
}