Cod sursa(job #1971315)

Utilizator vladm98Munteanu Vlad vladm98 Data 20 aprilie 2017 11:13:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;
int Pi[4000005];
char s[4000005];
int poz = 0;
vector <int> v;
ofstream fout ("strmatch.out");
void KMP (int n, int l)
{
    for (int i = 2; i<=n; ++i)
    {
        Pi[i] = Pi[i-1];
        while (Pi[i] && s[i]!=s[Pi[i]+1]) Pi[i] = Pi[Pi[i]];
        if (s[i] == s[Pi[i]+1]) ++Pi[i];
        if (Pi[i] == l)
        {
            ++poz;
            if (poz<=1000)
                v.push_back(i-l-l-1);
        }
    }
    fout << poz << '\n';
    for (auto x:v)
        fout << x << " ";
}
int main()
{
    ifstream fin ("strmatch.in");
    fin >> (s+1);
    int n = strlen(s+1), l;
    l = n;
    s[n+1] = '%';
    fin >> (s+n+2);
    n = strlen(s+1);
    KMP(n, l);
    return 0;
}