Pagini recente » Cod sursa (job #880394) | Cod sursa (job #2295327) | Cod sursa (job #2736279) | Cod sursa (job #2158638) | Cod sursa (job #2735638)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
const int baza=123;
const int mod1=100007;
const int mod2=100021;
char A[2000001];
char B[2000001];
vector <int> v;
int main()
{
cin>>A;
cin>>B;
int n=0,n1=strlen(B);
int m=strlen(A);
int put1=1;
int put2=1;
int rmod1=0,rmod2=0,bmod1=0,bmod2=0;
int i,c,c1;
for (i=0;i<m && i<n1;i++){
c=A[i];
rmod1=(rmod1*baza+c)%mod1;
rmod2=(rmod2*baza+c)%mod2;
c=B[i];
bmod1=(bmod1*baza+c)%mod1;
bmod2=(bmod2*baza+c)%mod2;
put1=(put1*baza)%mod1;
put2=(put2*baza)%mod2;
}
if (m>n1){
cout<<0;
return 0;
}
if (rmod1==bmod1 && rmod2==bmod2){
v.push_back(0);///i-m+1;
n++;
}
for (;B[i];i++){
c=B[i];
c1=B[i-m];
bmod1=((bmod1-(put1*c1)%mod1+mod1)*baza+c)%mod1;///+mod1 ca sa fie pozitiv
bmod2=((bmod2-(put2*c1)%mod2+mod2)*baza+c)%mod2;
if (rmod1==bmod1 && rmod2==bmod2 && n<1000) v.push_back(i-m+1),n++;
}
cout<<n<<"\n";
for (i=0;i<n;i++){
cout<<v[i]<<" ";
}
return 0;
}