Cod sursa(job #812682)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 14 noiembrie 2012 11:08:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#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;
    q1 = q2 = 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;
}