Cod sursa(job #2284725)

Utilizator httpsLup Vasile https Data 17 noiembrie 2018 14:01:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#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 = 0;
    for(int i = 2; pattern[i]; ++i) {
        while(pattern[k+1] != pattern[i] && k) k = pref[k];
        if(pattern[k+1] == pattern[i]) ++k;
        pref[i] = k;
    }

}

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

    int k = 0;
    int len_pattern = strlen(pattern+1);

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

        if(k == len_pattern) res.push_back(i - len_pattern), 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;
}