Pagini recente » Cod sursa (job #1587327) | Cod sursa (job #2666391) | Cod sursa (job #1350106) | Cod sursa (job #1699371) | Cod sursa (job #812681)
Cod sursa(job #812681)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int M1 = 666013, M2 = 666001, MAXL = 2000010;
char c[MAXL],s[MAXL];
int n,i,j,m,hc1,hs1,hc2,hs2,q1,q2;
vector<int> sol;
int main() {
in>>c>>s;
q = 1;
for(i=0; i<strlen(c); i++)
hc1 = (hc1 * 26 + c[i] - 'A') % M1, q1 = (q1*26)%M1,
hc2 = (hc2 * 26 + c[i] - 'A') % M2, q2 = (q2*26)%M2;
q1 /= 26;
q2 /= 26;
for(i=0; i<strlen(c); i++)
hs1 = (hs1 * 26 + s[i] - 'A') % M1,
hs2 = (hs2 * 26 + s[i] - 'A') % M2;
if(hc1 == hs1 && hc2 == hs2)
sol.push_back(0);
for(i=strlen(c); i<strlen(s); i++) {
hs1 -= (q1 * (s[i - strlen(c)] - 'A')) % M1;
hs2 -= (q2 * (s[i - strlen(c)] - 'A')) % M2;
while(hs1 < 0)
hs1 += M1;
while(hs2 < 0)
hs2 += M2;
hs1 = (hs1 * 26 + s[i] - 'A') % M1;
hs2 = (hs2 * 26 + s[i] - 'A') % M2;
if(hc1 == hs1 && hc2 == hs2)
sol.push_back(i-strlen(c)+1);
}
out<<sol.size()<<'\n';
for(i=0; i<sol.size(); i++)
out<<sol[i]<<' ';
return 0;
}