Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2955161) | Autentificare | Cod sursa (job #2404153)
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#define mod 1000000007
#define baza 199
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s[2000005],gs[2000005];
long p,sum,sumtg,n,m,i,j,nr;
bool ok;
vector <int> ans;
int main()
{
fin>>gs;
fin>>s;
n=strlen(s);
m=strlen(gs);
p=1;
for(i=m-1;i>=0;i--)
{
sumtg+=gs[i]*p;
sumtg%=mod;
p*=baza;
p%=mod;
}
for(i=0;i<n-m+1;i++)
{
p=p%mod;
if(i==0)
{
p=1;
for(j=m-1;j>=0;j--)
{
sum+=s[j]*p;
sum%=mod;
p*=baza;
p%=mod;
}
}
else
{
sum*=baza;
sum%=mod;
sum+=s[i+m-1];
sum-=(s[i-1]*p)%mod;
if(sum<0)
sum+=mod;
sum%=mod;
}
if(sum==sumtg)
{
ok=true;
for(j=i;j<=i+m-1;j++)
{
if(s[j]!=gs[j-i])
{
ok=false;
break;
}
}
if(ok==true)
{
nr++;
ans.push_back(i);
}
}
}
if(n>1000)
{
fout<<nr<<'\n';
i=0;
for(auto par : ans)
{
i++;
fout<<par<<' ';
if(i==1000)
break;
}
return 0;
}
fout<<nr<<'\n';
for(auto par : ans)
fout<<par<<' ';
return 0;
}