Pagini recente » Cod sursa (job #1196135) | Cod sursa (job #806405) | Cod sursa (job #905439) | Cod sursa (job #635023) | Cod sursa (job #2802710)
#include<bits/stdc++.h>
using namespace std;
const int p=67;
const int mod = 1000000007;
vector<int> solutie;
char a[2000005],b[2000005];
long long H,H0,pw;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin>>a;
fin>>b;
H = 0;
int n=strlen(a);
int m=strlen(b);
for(int i=0;i<n;i++)
H = (H * p + a[i])%mod;
H0 =0;
for(int i=0;i<n;i++)
H0 = (H0 * p + b[i])%mod;
if(H == H0)
{
solutie.push_back(0);
}
pw = 1;
for(int i=1;i<n;i++)
pw = (pw * p) %mod;
//pw este p^(n-1)
for (int i=1;i<m;i++)
{
if((i+n-1)<m)
{
//b[i-1]
//Secventa noastra curenta incepe la b[i]. Cea de dinainte avea b[i-1]
//Trebuie sa scadem b[i-1] * p^(n-1)
H0 = (H0 - ( (pw*b[i-1])%mod ) + mod) %mod;
H0 = (H0 * p + b[i+n-1]) %mod;
if(H == H0)
{
solutie.push_back(i);
}
}
}
int sz = solutie.size();
fout<<solutie.size()<<'\n';
for(int i=0;i<min(1000,sz);i++)
fout<<solutie[i]<<' ';
return 0;
}