Cod sursa(job #1894942)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 27 februarie 2017 18:03:32
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <string>
#include <queue>
using namespace std;

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

string txt, pat;
queue<int> indx;
int T[2000010], i, j, sol;

void precomp() {
    int i = 1, j = 0;

    while (i < pat.length()) {
        if (pat[ i ] == pat[ j ]) {
            T[ i ] = j + 1;
            i++; j++;
        } else if (j != 0) {
            while (j != 0 && pat[ i ] != pat[ j ])
                j = T[ j - 1 ];
        } else {
            i++;
        }
    }
}

int main()
{
    fin >> pat >> txt;
    txt.push_back('.');

    precomp();

    i = 0; j = 0;
    while (i <= txt.length()) {
        if (j >= pat.length()) {
            if (indx.size() < 1000)
                indx.push(i - pat.length());
            sol++;
            j = T[ j - 1 ];
        }
        if (txt[ i ] == pat[ j ]) {
            i++; j++;
        } else if (j != 0) {
            j = T[ j - 1 ];
        } else {
            i++;
        }
    }

    fout << sol << '\n';
    while(!indx.empty()) {
        fout << indx.front() << ' ';
        indx.pop();
    }

    return 0;
}