Cod sursa(job #1815937)

Utilizator vladm98Munteanu Vlad vladm98 Data 25 noiembrie 2016 22:36:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;
char s[4000005];
long long counter, raspuns[1001];
int Pi[4000005];
void KMP (long long lungime, long long n)
{
    for (long long i = 2; i<=n; ++i)
    {
        Pi[i] = Pi[i-1];
        while (Pi[i] && s[Pi[i]+1] != s[i]) Pi[i] = Pi[Pi[i]];
        if (s[i] == s[Pi[i]+1])
            ++Pi[i];
        if (Pi[i] == lungime)
        {
            ++counter;
            if (counter <= 1000)
                raspuns[counter] = i-2*lungime-1;
        }
    }
}
int main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    long long n, len;
    fin >> (s+1);
    len = strlen(s+1);
    s[len+1] = '#';
    fin >> (s+len+2);
    n = strlen(s+1);
    KMP(len, n);
    fout << counter << '\n';
    for (int i = 1; i<=counter && i <=1000; ++i)
        fout << raspuns[i] << " ";
    return 0;
}