Pagini recente » Cod sursa (job #1668424) | Cod sursa (job #822060) | Cod sursa (job #155575) | Cod sursa (job #2332749) | Cod sursa (job #2878261)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int base=29;
const int mod=66667;
int hashA,hashB;
int power=1;
const int NMAX=2e6+5;
char a[NMAX],b[NMAX];
int lenghtA,lenghtB;
int cnt;
int solutions[1001];
int precalculate()
{
for(int i=1;i<=lenghtA-1;i++)
{
power=(1LL*power*base)%mod;
}
return power;
}
int Create_HashA()
{
for(int i=0;i<lenghtA;i++)
{
hashA=((1LL*hashA*base)%mod+a[i]-'A')%mod;
}
}
int FindMatches()
{
for(int i=0;i<lenghtA;i++)
{
hashB=((1LL*hashB*base)%mod+b[i]-'A')%mod;
}
if(hashB==hashA)
{
cnt++;
if(cnt<=1000)
solutions[cnt]=1;
}
for(int i=lenghtA;i<lenghtB;i++)
{
hashB=(hashB-((1LL*(b[i-lenghtA]-'A')*power)%mod)+mod)%mod;
hashB=((1LL*hashB*base)%mod+b[i]-'A')%mod;
if(hashA==hashB)
{
cnt++;
if(cnt<=1000)
solutions[cnt]=i-lenghtA+1;
}
}
}
int main()
{
cin>>a>>b;
lenghtA=strlen(a);
lenghtB=strlen(b);
precalculate();
Create_HashA();
FindMatches();
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
cout<<solutions[i]<<" ";
return 0;
}