Cod sursa(job #1316709)

Utilizator retrogradLucian Bicsi retrograd Data 14 ianuarie 2015 00:48:22
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<vector>
#include<cstring>
#define MAXN 2000002
#define SOLSIZE 1000

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char c, WORD[MAXN];
int PI[MAXN+1], wordlen;

#define PI (PI+1)

void process() {
    fin>>WORD[0];
    PI[0] = -1;
    int i, cnd = 0;
    for(i=0; WORD[i++] != '\n';) {
        fin>>noskipws>>WORD[i];
        while(cnd != -1 && WORD[i] != WORD[cnd]) cnd = PI[cnd];
        if(cnd == -1) {
            cnd = 0;
            PI[i] = 0;
        } else {
            cnd++;
            PI[i] = cnd;
        }
    }
    WORD[i] = 0;
    wordlen = i-1;
}

vector<int> SOL;
int ap;

void search() {
    int stare = 0;
    for(int i=0; fin>>noskipws>>c, c != '\n';i++) {
        while(c != WORD[stare] && stare != -1) {
            stare = PI[stare];
        }
        if(stare == -1) {
            stare = 0;
        } else {
            stare ++;
            if(stare == wordlen) {
                ap++;
                if(SOL.size() <= SOLSIZE)
                    SOL.push_back(i);
                stare = PI[stare-1];
            }
        }

    }
}

void afis() {
    fout<<ap<<'\n';
    for(vector<int>::iterator it=SOL.begin(); it!=SOL.end(); ++it) {
        fout<<*it - wordlen + 1<<" ";
    }
}

int main() {
    process();
    search();
    afis();
    return 0;
}