Cod sursa(job #1995497)

Utilizator FredyLup Lucia Fredy Data 28 iunie 2017 02:33:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("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()
{

    fin>>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);
    }

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