Cod sursa(job #3131450)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 20 mai 2023 11:51:07
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int NMAX = 2e6;

char a[NMAX + 1], b[NMAX + 1];
int lps[NMAX];
int positions[1001], ind = 0;

void LPS(char s[])
{
    int n = strlen(s);
    int i = 1, j = 0;
    while (i < n)
    {
        if (s[i] == s[j])
        {
            j++;
            lps[i] = j;
            i++;
        }
        else
        {
            if (j > 0)
                j = lps[j - 1];
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int KMP(char a[], char b[])
{
    LPS(b);

    int n = strlen(a);
    int m = strlen(b);

    int i = 0, j = 0;
    while ((n - i) >= (m - j))
    {
        if (a[i] == b[j])
        {
            i++;
            j++;
        }

        if (j == m)
        {
            if(ind < 1000)
                positions[ind++] = i - j; 
            j = lps[j - 1];
        }
        else if (i < n && a[i] != b[j])
        {
            if (j > 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

int main()
{
    cin >> a >> b;
    KMP(b, a);

    cout << ind << '\n';
    for(int i = 0; i < ind; i++)
        cout << positions[i] << ' ';
        
    return 0;
}