Cod sursa(job #2284729)

Utilizator httpsLup Vasile https Data 17 noiembrie 2018 14:12:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
///cu indexare de la 0
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

#define NMAX 2000001

char pattern[NMAX], text[NMAX];
int pref[NMAX];

void make_prefix(char pattern[])
{
    int k = -1;
    pref[0] = -1;
    for(int i = 1; pattern[i]; ++i) {
        while(pattern[k+1] != pattern[i] && k != -1) k = pref[k];
        if(pattern[k+1] == pattern[i]) ++k;
        pref[i] = k;
    }

}

int main()
{
    fin>>pattern>>text;
    make_prefix(pattern);

    int k = -1;
    int len_pattern = strlen(pattern);

    vector<int> res;
    for(int i = 0; text[i]; ++i) {
        while(pattern[k+1] != text[i] && k != -1) k = pref[k];
        if(pattern[k+1] == text[i]) ++k;

        if(k+1 == len_pattern) res.push_back(i - len_pattern + 1), k = pref[k];
    }

    fout<<res.size()<<'\n';
    k = min((int)res.size(), 1000);
    for(int i = 0; i < k; ++i)
        fout<<res[i]<<' ';

    return 0;
}