Pagini recente » Cod sursa (job #3322530) | Cod sursa (job #1789436) | Cod sursa (job #1628152) | Cod sursa (job #2888591) | Cod sursa (job #3353880)
#include <fstream>
#include <cstring>
using namespace std;
char s1[2000001], s2[2000001], v[2000001];
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main(){
int l1, l2, p1=1, p2=1, nrs1=0, nrs2=0, i;
const int b=63, N1=100007, N2=100021; ///baza 63, N1 si N2 sunt numerele prime mari
cin>>s1>>s2;
l1=strlen(s1);
l2=strlen(s2);
for( i = 0; i < l1; i++ ){ ///calculam resturile la imp cu N1 resp. N2 ale secventei pe care o cautam
nrs1=(nrs1*b+s1[i])%N1;
nrs2=(nrs2*b+s1[i])%N2;
if( i != 0 ){ ///crestem puterea doar daca nu suntem pe primul element
p1=(p1*b)%N1;
p2=(p2*b)%N2;
}
}
if( l1 > l2 ) //daca lungimea lui s1 e mai mare decat s2, atunci nu poate aparea in s2
cout<<0;
else{
int nr1=0, nr2=0;
for( i = 0; i < l1; i++ ){ ///calculam resturile la imp cu N1 resp. N2 ale primei secvente din s2
nr1=(nr1*b+s2[i])%N1;
nr2=(nr2*b+s2[i])%N2;
}
int k=0;
if( nr1 == nrs1 && nr2 == nrs2 ) ///verificam prima secventa
v[k++]=1;
for( i = l1; i < l2; i++ ){ ///verificam toate celelalte secvente
///scot s2[i-l1] si adaug s2[i]
nr1=((nr1-(s2[i-l1]*p1)%N1+N1)*b+s2[i])%N1;
nr2=((nr2-(s2[i-l1]*p2)%N2+N2)*b+s2[i])%N2;
if( nr1 == nrs1 && nr2 == nrs2 ){ ///daca secventa e buna
v[i-l1+1]=1;
k++;
}
}
cout<<k<<'\n';
k=0;
for( i = 0; i < l2 && k < 1000; i++ ) ///afisez primele 1000 de pozitii ale secventelor bune
if( v[i] == 1 ){
k++;
cout<<i<<' ';
}
}
return 0;
}