Pagini recente » Cod sursa (job #188016) | Cod sursa (job #3273277) | Cod sursa (job #3272825) | Cod sursa (job #2753097) | Cod sursa (job #3215779)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001],B[2000001];
const int M1=100007;
const int M2=100021;
long P1=1,P2=1;
long long hash1A,hash1B;
long long hash2A,hash2B;
int NA,NB;
vector<int> ans;
int main()
{
cin>>A>>B;
NA=strlen(A);
NB=strlen(B);
if(NA>NB)
{
cout<<0;
return 0;
}
for(int i=0;i<NA;i++)
{
hash1A=(hash1A*256+A[i])%M1;
hash1B=(hash1B*256+B[i])%M1;
hash2A=(hash2A*256+A[i])%M2;
hash2B=(hash2B*256+B[i])%M2;
if(i)
{
P1=(P1*256*1LL)%M1;
P2=(P2*256*1LL)%M2;
}
}
if(hash1A==hash1B && hash2A==hash2B)
ans.push_back(0);
for(int i=1;i<=NB-NA;i++)
{
hash1B=((((hash1B-B[i-1]*P1)%M1+M1)*256%M1)+B[i+NA-1])%M1;
hash2B=((((hash2B-B[i-1]*P2)%M2+M2)*256%M2)+B[i+NA-1])%M2;
if(hash1A==hash1B && hash2A==hash2B)
ans.push_back(i);
}
cout<<ans.size()<<'\n';
for(int i=0;i<min((int) ans.size(),1000);i++)
cout<<ans[i]<<" ";
return 0;
}