Pagini recente » Cod sursa (job #1917758) | Cod sursa (job #2301696) | Cod sursa (job #25453) | Cod sursa (job #1891201) | Cod sursa (job #847901)
Cod sursa(job #847901)
#include <fstream>
#include <string>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string a,b;
int h1,k1,h2,k2,n,m,i,v[3000000],vn;
const int mod1=1000021,mod2=1000007;
int main(){
fi >> a >> b; n = a.size(); m = b.size();
if (n>m) { fo << "0"; return 0; }
for (i=0; i<n; i++){
k1 += a[i] % mod1; k2 += a[i] % mod2;
h1 += b[i] % mod1; h2 += b[i] % mod2;
}
if ((k1==h1)&&(k2=h2)&&(b.substr(0,n)==a)) vn++;
for (i=n; i<m; i++){
h1 = (h1-b[i-n]+b[i])%mod1; h2 = (h2-b[i-n]+b[i])%mod2;
if ((k1==h1)&&(k2=h2)&&(b.substr(i-n+1,n)==a)) v[vn++] = i-n+1;
}
fo << vn << "\n";
for (i=0; i<vn && i<1000; i++) fo << v[i] << " ";
return 0;
}