Pagini recente » Cod sursa (job #2555228) | Cod sursa (job #3132109) | Cod sursa (job #3270720) | Cod sursa (job #119882) | Cod sursa (job #812679)
Cod sursa(job #812679)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatchin");
ofstream out("strmatch.out");
const int M = 666013, MAXL = 2000010;
char c[MAXL],s[MAXL];
int n,i,j,m,hc,hs,q;
vector<int> sol;
int main() {
in>>c>>s;
q = 1;
for(i=0; i<strlen(c); i++)
hc = (hc * 26 + c[i] - 'A') % M, q = (q*26)%M;
q /= 26;
for(i=0; i<strlen(c); i++)
hs = (hs * 26 + s[i] - 'A') % M;
if(hc == hs)
sol.push_back(0);
for(i=strlen(c); i<strlen(s); i++) {
hs -= (q * (s[i - strlen(c)] - 'A')) % M;
while(hs < 0)
hs += M;
hs = (hs * 26 + s[i] - 'A') % M;
if(hc == hs)
sol.push_back(i-strlen(c)+1);
}
out<<sol.size()<<'\n';
for(i=0; i<sol.size(); i++)
out<<sol[i]<<' ';
return 0;
}