Pagini recente » Cod sursa (job #1759880) | Cod sursa (job #1720933) | Cod sursa (job #2447110) | Cod sursa (job #1647078) | Cod sursa (job #2764334)
#include<iostream>
#include<fstream>
#include<string.h>
#define mod 100007
#define p 140
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000005],sir2[2000005];
long long int n,m,i,j,c,nr,nr1,nr2,prima,ultima,ind,putere;
int main()
{
fin.getline(sir1,2000005);
//cin.get();
fin.getline(sir2,2000005);
n=strlen(sir1);
m=strlen(sir2);
nr1=0;
for(i=0;i<n;i++)
{
nr=sir1[i];
nr1=(nr1*p+nr)%mod;
}
putere=1;
for(i=0;i<n;i++)
{
if(i>0)
putere=(putere*p)%mod;
nr=sir2[i];
nr2=(nr2*p+nr)%mod;
}
if(nr2==nr1)
c++;
ultima=nr;
for(i=n;i<m;i++)
{
nr=sir2[i];
prima=sir2[i-n];
nr2=(nr2-prima*putere)%mod;
nr2=(nr2+mod)%mod;
nr2=(nr2*p+nr)%mod;
//cout<<nr2<<" "<<nr1<<"\n";
if(nr2==nr1)
{
c++;
}
}
fout<<c<<"\n";
putere=1;
nr=0;
nr2=0;
for(i=0;i<n;i++)
{
if(i>0)
putere=(putere*p)%mod;
nr=sir2[i];
nr2=(nr2*p+nr)%mod;
}
if(nr2==nr1)
c++;
ultima=nr;
for(i=n;i<m;i++)
{
nr=sir2[i];
prima=sir2[i-n];
nr2=(nr2-prima*putere)%mod;
nr2=(nr2+mod)%mod;
nr2=(nr2*p+nr)%mod;
//cout<<nr2<<" "<<nr1<<"\n";
if(nr2==nr1)
{
fout<<i-n+1<<" ";
c++;
}
}
fin.close();
fout.close();
return 0;
}