Cod sursa(job #812679)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 14 noiembrie 2012 11:04:12
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#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;
}