Pagini recente » Cod sursa (job #1294159) | Monitorul de evaluare | Cod sursa (job #1109825) | Cod sursa (job #3183263) | Cod sursa (job #2419117)
#include <iostream>
#include <fstream>
#include <cstring>
#define MOD 100000000007
#define LMAX 2000003
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str1;
string str2;
int r=-1, n,m,i;
unsigned long long k, h1, h2,b;
int rs[1001];
unsigned long long pow(int a, int b)
{
if(b==0)
return 1;
unsigned long long x = pow(a, b/2);
if(b%2==0)
return (x*x)%MOD;
return (x*x*a)%MOD;
}
int main()
{
fin>>str1>>str2;
int lp = str1.size()-1;
n = str1.size();
m = str2.size();
b=1;
for(i=n-1;i>=0; i--)
{
k=(k+(str1[i]-'A')*b)%MOD;
h1+=((str2[i]-'A')*b)%MOD;
b=(b*31)%MOD;
}
/* for(int i=0; i<=lp; i++)
{
k+=((str1[i]-'A')*pow(31, lp-i))%MOD;
h1+=((str2[i]-'A')*pow(31, lp-i))%MOD;
}*/
if(k==h1)
rs[++r]=0;
// cout<<h1<<' '<<k<<'\n';
int st;
int dr;
for(i=n; i<m; i++)
{
//h2=((h1*31)%MOD-((str2[st-1]-'A')*pow(31, lp))%MOD+str2[dr]-'A')%MOD;
h1=(((h1*31)%MOD-((str2[i-n]-'A')*b)%MOD)%MOD+str2[i]-'A')%MOD;
h1=(h1+MOD)%MOD;
// h2*=31;
if(k==h1 && r<1000)
rs[++r]=i-n+1;
else if(k==h2)
r++;
//cout<<h1<<'\n';
}
r = min(r,999);
fout<<r+1<<'\n';
for(i=0; i<=r; i++)
fout<<rs[i]<<' ';
return 0;
}