Cod sursa(job #1316720)

Utilizator retrogradLucian Bicsi retrograd Data 14 ianuarie 2015 01:52:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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;

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

int SOL[1001], solsize;
int ap;

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

void afis() {
    fout<<ap<<'\n';
    for(int i=0; i<solsize; i++) {
        fout<<SOL[i]<<" ";
    }
}

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