Cod sursa(job #2434299)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 1 iulie 2019 14:44:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int pref[2000005];
char a[2000005], b[2000005];
int rez[2000005], rez1;
void prefix()
{
    int m = strlen(a);
    int len = 0;
    pref[0] = 0;

    for(int i = 1 ; a[i] ; i ++)
    {
        while( len > 0 && a[i] != a[len]) len = pref[len];
        if(a[i] == a[len]) len++;
        pref[i] = len;
    }

}
void kmp()
{
    prefix();
    int n = strlen(b);
    int m = strlen(a);
    int i = 0, j = 0;
    while( i < n)
    {
        if(b[i] == a[j])
            i++, j++;
        if(j == m)
            rez[++rez1] = i - j, j = pref[j - 1];
        else if (i < n && b[i] != a[j])
        {
            if(j > 0)
                j = pref[j - 1];
            else
                i++;
        }

    }
    cout << rez1 << '\n';
    (rez1 > 1000) ? rez1 = 1000 : rez1 = rez1;

    for(int i = 1 ; i <= rez1 ; i++)
        cout << rez[i] << ' ';
}
int main()
{
    cin >> a;
    cin >> b;
    kmp();
    return 0;
}