Cod sursa(job #1409928)

Utilizator httpsLup Vasile https Data 30 martie 2015 19:37:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

#ifdef INFOARENA
ifstream f("strmatch.in");
#define cout g
#else
ifstream f("date.in");
#endif // INFOARENA

ofstream g("strmatch.out");

#define nmax 2000001

char pattern[nmax],text[nmax];
int pref[nmax],n,m,k,pos,i,nr;
vector <int> sol;

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

int main()
    {

    f>>pattern+1>>text+1;
    n=strlen(pattern+1);
    m=strlen(text+1);
    make_prefix();

    for(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);
    }
    cout<<sol.size()<<'\n';
    for(auto x:sol)
    {cout<<x-1<<' ';
    if(++nr==1000) break;
    }
    return 0;
    }