Pagini recente » Cod sursa (job #3041135) | Cod sursa (job #85327) | Cod sursa (job #1319820) | Cod sursa (job #1902124) | Cod sursa (job #3003546)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001],B[2000001];
int hash1A,hash2A,hash1,hash2;
int P1,P2,M1,M2,nr;
vector<int> pozitii;
int main()
{
cin>>A;
cin>>B;
int NA=strlen(A);
int NB=strlen(B);
P1=1;
P2=1;
const int M1=100007;
const int M2=100021;
if(NA>NB)
{
cout<<0;
return 0;
}
for(int i=0;i<NA;i++)
{
hash1A=(hash1A*216+A[i])%M1;
hash2A=(hash2A*216+A[i])%M2;
hash1=(hash1*216+B[i])%M1;
hash2=(hash2*216+B[i])%M2;
if(i!=0)
{
P1=(P1*216)%M1;
P2=(P2*216)%M2;
}
}
if(hash1==hash1A && hash2==hash2A)
{
nr++;
pozitii.push_back(0);
}
for(int i=1;i<=NB-NA;i++)
{
hash1=(((hash1-(B[i-1]*P1))%M1+M1)*216+B[i+NA-1])%M1;
hash2=(((hash2-(B[i-1]*P2))%M2+M2)*216+B[i+NA-1])%M2;
if(hash1A==hash1 && hash2A==hash2)
{
nr++;
pozitii.push_back(i);
}
}
cout<<nr<<'\n';
if(nr>1000)
for(int i=0;i<1000;i++)
cout<<pozitii[i]<<" ";
else
for(int i=0;i<nr;i++)
cout<<pozitii[i]<<" ";
return 0;
}