Pagini recente » Cod sursa (job #3229365) | Cod sursa (job #2506381) | Cod sursa (job #425198) | Cod sursa (job #1927260) | Cod sursa (job #2763712)
#include<iostream>
#include<fstream>
#include<string.h>
#define mod 100007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000005],sir2[2000005];
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]-'A'+1;
nr1=(nr1*27+nr)%mod;
}
putere=1;
for(i=0;i<n;i++)
{
if(i>0)
putere=(putere*27)%mod;
nr=sir2[i]-'A'+1;
nr2=(nr2*27+nr)%mod;
}
if(nr2==nr1)
c++;
ultima=nr;
for(i=n;i<m;i++)
{
nr=sir2[i]-'A'+1;
prima=sir2[i-n]-'A'+1;
nr2=(nr2-prima*putere)%mod;
nr2=(nr2+mod)%mod;
nr2=(nr2*27+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*27)%mod;
nr=sir2[i]-'A'+1;
nr2=(nr2*27+nr)%mod;
}
if(nr2==nr1)
c++;
ultima=nr;
for(i=n;i<m;i++)
{
nr=sir2[i]-'A'+1;
prima=sir2[i-n]-'A'+1;
nr2=(nr2-prima*putere)%mod;
nr2=(nr2+mod)%mod;
nr2=(nr2*27+nr)%mod;
//cout<<nr2<<" "<<nr1<<"\n";
if(nr2==nr1)
{
fout<<i-n+1<<" ";
c++;
}
}
fin.close();
fout.close();
return 0;
}