Cod sursa(job #2163961)

Utilizator c0mradec0mrade c0mrade Data 12 martie 2018 20:45:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int nx=2000002;

char N[nx],M[nx];

int pref[nx];

void Prefix(char N[])
{
    int n=strlen(N);

    int k=0;

    for(int i=1; i<n; i++)
    {
        while(N[i]!=N[k] && k>0)
            k=pref[k-1];
        if(N[i]==N[k])
            k++;
        pref[i]=k;
    }
}

vector < int > v;

void kmp (char N[], char M[])
{
    Prefix(N);

    int k=0;
    int x=strlen(M);
    int y=strlen(N);

    for(int i=0; i<x; i++)
    {
        while(N[k]!=M[i] && k>0)
            k=pref[k-1];

        if(N[k]==M[i])
            k++;

        if(k==y)
            v.push_back(i-k+1);
    }
}
int main()
{
    in>>N>>M;

    kmp(N,M);

    out<<v.size()<<'\n';

    for(int i=0; i<min((int)v.size(),1000); i++)
        out<<v.at(i)<<' ';

    return 0;
}