Cod sursa(job #2434200)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 1 iulie 2019 00:16:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 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 n = strlen(b);
    int m = strlen(a);
    int len = 0;
    pref[0] = 0;
    int i = 1;
    while(i < m)
        if(a[i] == a[len])
        {
            len++;
            pref[i] = len;
            i++;

        }
        else
        {
            if( len > 0)
                len = pref[len-1];
            else
                pref[i] = 0, i++;
        }
    /*for( j = 0 ; j <  m ; j++)
        cout << pref[j] << ' ';
    cout << '\n';*/
}
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++;
        }

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