Cod sursa(job #2765907)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 30 iulie 2021 12:33:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define NMAX 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[NMAX], b[NMAX];
int lps[NMAX], nr, n, m;
vector <int> ans;

void init()
{
    int l = 0;
    lps[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        while(l && a[l + 1] != a[i])
            l = lps[l];
        if(a[i] == a[l + 1])
            l++;
        lps[i] = l;
    }
}

void kmp()
{
    int l = 0;
    for(int i = 1; i <= m; i++)
    {
        while(l && a[l + 1] != b[i])
            l = lps[l];
        if(a[l + 1] == b[i])
            l++;
        if(l == n)
        {
            l = lps[n];
            nr++;
            if(nr <= 1000)
                ans.push_back(i - n);
        }
    }
}

int main()
{
    f >> a + 1 >> b + 1;
    n = strlen(a + 1);
    m = strlen(b + 1);

    init();
    kmp();

    g << nr << "\n";
    for(auto k : ans)
        g << k << " ";

    return 0;
}