Cod sursa(job #2042261)

Utilizator FredyLup Lucia Fredy Data 18 octombrie 2017 11:37:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

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

#define lim 2000020
int n,m,pref[lim];
char pattern[lim],text[lim];
vector <int> sol;

void prefix_function()
{
    for (int i=2; i<=n; i++)
    {
        int k=pref[i-1];
        while (k && pattern[k+1] != pattern[i]) k=pref[k];
        if (pattern[k+1] == pattern[i]) k++;
        pref[i]=k;
    }
}


int main()
{
    fin>>(pattern+1)>>(text+1);
    n=strlen(pattern+1);
    m=strlen(text+1);

    prefix_function();

    int pos=0;
    for (int i=1; i<=m; i++)
    {
        while (pattern[pos+1] != text[i] && pos)    pos=pref[pos];
        if (pattern[pos+1] == text[i]) ++pos;
        if (pos==n) sol.emplace_back(i-pos+1);
    }

    int nr=0;
    fout<<sol.size()<<'\n';
    for (auto x:sol)
    {
        fout<<x-1<<' ';
        if (++nr==1000)
            break;
    }

    fin.close();
    fout.close();
    return 0;
}