Cod sursa(job #1745595)

Utilizator jason2013Andronache Riccardo jason2013 Data 22 august 2016 12:05:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<bits/stdc++.h>

using namespace std;

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

const int NMax = 2000005;
char s[NMax],P[NMax];
int n,m,i,j,q,k,stare[NMax],nr;

vector <int> sl;

void prefix()
{
    stare[1] = 0;
    k = 0;
    for(q = 2; q <= m; q++)
    {
        while(k > 0 && P[k + 1] != P[q])
            k = stare[k];
        if(P[k + 1] == P[q])
            k++;
        stare[q] = k;
    }
}

void kmp()
{
    prefix();
    q = 0;
    for(i = 1; i <= n; i++)
    {
        while(q > 0 && P[q + 1] != s[i])
            q = stare[q];
        if(P[q + 1] == s[i])
            q++;
        if(q == m)
        {
            nr++;
            if(nr<=1000)
                sl.push_back(i - m);
            q = stare[q];
        }
    }
}

int main()
{
    fin.get(P+1,2000001);
    fin.get();
    fin.get(s+1,2000001);
    n = strlen(s+1);
    m = strlen(P+1);
    kmp();
    fout<<nr<<'\n';
    for(i = 0 ; i < sl.size(); i++)
        fout<<sl[i]<<" ";
    return 0;
}