Pagini recente » Cod sursa (job #1260169) | Cod sursa (job #2424044) | Cod sursa (job #2798949) | Cod sursa (job #1840983) | Cod sursa (job #3030345)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001],B[2000001];
int NA,NB;
const int M1=100021;
const int M2=100007;
long long hash1,hash2,hash1B,hash2B;
long long P1,P2;
long long nr;
vector<int> pozitii;
int main()
{
cin>>A>>B;
NA=strlen(A);
NB=strlen(B);
if(NA>NB)
{
cout<<0;
return 0;
}
P1=1;
P2=1;
for(int i=0;i<NA;i++)
{
hash1=(hash1*256+A[i])%M1;
hash2=(hash2*256+A[i])%M2;
hash1B=(hash1B*256+B[i])%M1;
hash2B=(hash2B*256+B[i])%M2;
if(i)
{
P1=(P1*256)%M1;
P2=(P2*256)%M2;
}
}
if(hash1==hash1B && hash2==hash2B)
{
nr++;
pozitii.push_back(0);
}
for(int i=1;i<=NB-NA;i++)
{
hash1B=(((hash1B-B[i-1]*P1)%M1+M1)*256+B[i+NA-1])%M1;
hash2B=(((hash2B-B[i-1]*P2)%M2+M2)*256+B[i+NA-1])%M2;
if(hash1==hash1B && hash2==hash2B)
{
nr++;
pozitii.push_back(i);
}
}
cout<<nr<<'\n';
if(nr<=1000)
for(int i=0;i<pozitii.size();i++)
cout<<pozitii[i]<<" ";
else
for(int i=0;i<1000;i++)
cout<<pozitii[i]<<" ";
return 0;
}