Pagini recente » JohnnyCode | Borderou de evaluare (job #1410156) | Borderou de evaluare (job #3331908) | JohnnyCode | Cod sursa (job #3334653)
#include <iostream>
#include <cstring>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int N;
vector <int> ans;
const int Base = 63;
const int MOD1 = 1e9+7;
const int MOD2 = 1e9+9;
char A[2000001],B[2000001];
long long hashA1,hashA2;
long long hashB1,hashB2;
long long P1=1,P2=1;
void Citire(){
fin>>A>>B;
}
bool Verificare(int st,int dr){
for (int i=st;i<=dr;++i)
if (A[i-st]!=B[i])
return false;
return true;
}
void Rezolvare(){
int nA=strlen(A),nB=strlen(B);
if (nA>nB)
return;
P1=1,P2=1;
for (int i=0;i<nA;++i){
hashA1=(hashA1*Base+A[i])%MOD1;
hashA2=(hashA2*Base+A[i])%MOD2;
if (i!=0){
P1=(P1*Base)%MOD1;
P2=(P2*Base)%MOD2;
}
}
for (int i=0;i<nA;++i){
hashB1=(hashB1*Base+B[i])%MOD1;
hashB2=(hashB2*Base+B[i])%MOD2;
}
if (hashA1==hashB1 && hashA2==hashB2)
if (Verificare(0,nA-1)){
N++;
ans.push_back(0);
}
for (int i=nA;i<nB;++i){
hashB1=(((hashB1-B[i-nA]*P1)%MOD1+MOD1)*Base+B[i])%MOD1;
hashB2=(((hashB2-B[i-nA]*P2)%MOD2+MOD2)*Base+B[i])%MOD2;
if (hashA1==hashB1 && hashA2==hashB2)
if (Verificare(i-nA+1,i)){
N++;
if (N<1000)
ans.push_back(i-nA+1);
}
}
}
void Afisare(){
fout<<N<<"\n";
for (auto i:ans)
fout<<i<<' ';
}
int main()
{
Citire();
Rezolvare();
Afisare();
return 0;
}