Pagini recente » Cod sursa (job #2701754) | Cod sursa (job #2369176) | Cod sursa (job #2098333) | Cod sursa (job #1712204) | Cod sursa (job #847966)
Cod sursa(job #847966)
#include <fstream>
#include <string>
#include <iostream>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string a,b;
int p2,h2,k2,p1,h1,k1,n,m,i,v[3000000],vn;
const int mod1=100021,mod2=100007,p=73;
int main(){
fi >> a >> b; n = a.size(); m = b.size();
if (n>m) { fo << "0"; return 0; }
p1=1; p2=1;
for (i=0; i<n; i++){
k1 = (k1*p+a[i]) % mod1; k2 = (k2*p+a[i]) % mod2;
h1 = (h1*p+b[i]) % mod1; h2 = (h2*p+b[i]) % mod2;
if (i) {p1 = (p1*p) % mod1; p2 = (p2*p)%mod2;}
}
if ((k2==h2)&&(k1==h1)) vn++;
for (i=n; i<m; i++){
h1 = ((h1-(b[i-n]*p1)%mod1+mod1)*p+b[i])%mod1;
h2 = ((h2-(b[i-n]*p2)%mod2+mod2)*p+b[i])%mod2;
if ((k2==h2)&&(k1==h1)) v[vn++] = i-n+1;
}
fo << vn << "\n";
for (i=0; i<vn && i<1000; i++) fo << v[i] << " ";
return 0;
}