Cod sursa(job #3246003)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 1 octombrie 2024 15:01:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "strmatch";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const int NMAX = 2e6 + 5;

int n;

int cnt;

int pi[NMAX * 2];

std :: string s;

std :: string t;

void kmp()
{
    for(int i = 1; i < s.size(); i ++)
    {
        int j = pi[i - 1];

        while(j > 0 && s[i] != s[j])
        {
            j = pi[j - 1];
        }

        if(s[i] == s[j])
        {
            j ++;
        }

        pi[i] = j;
    }
}

int main()
{

    f >> t;

    s += t;

    n = t.size();

    s += '#';

    f >> t;

    s += t;

    kmp();

    for(int i = 0; i < s.size(); i ++)
    {
        if(pi[i] == n)
        {
            cnt ++;
        }
    }

    g << cnt << '\n';

    cnt = 0;

    for(int i = 0; i < s.size(); i ++)
    {
        if(pi[i] == n)
        {
            cnt ++;

            std :: cout << i << " ";

            g << i - 2 * n << " ";

            if(cnt == 1000)
            {
                return 0;
            }
        }
    }

    return 0;
}