Cod sursa(job #3147822)

Utilizator stanciu_anaStanciu Ana-Maria stanciu_ana Data 27 august 2023 14:11:25
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char sir1[2000005], sir2[2000005];
int v[25];
int cnt;
int poz[1005];

int main()
{
    cin >> sir1 >> sir2;
    int i = 1, j = 0;
    int lg = strlen(sir1);
    while(i < lg)
    {
        while(sir1[i] != sir1[j] && j != 0)
            j = v[j-1];
        if(sir1[i] == sir1[j])
           {
              v[i] = v[i-1] + 1;
              i++;
              j++;
           }
        else
        {
            v[i] = 0;
            i++;
        }

    }
    int k = 1;
    i = 1;
    int lg2 = strlen(sir2);
    while(k < lg2-1)
    {
        while(sir1[i] == sir2[k] && i < lg-1)
        {
            i++;
            k++;
        }
        if(i == lg-1 && sir1[i] == sir2[k])
        {
            cnt++;
            poz[cnt] = k - i;
            i = v[i-1];
        }
        while(sir1[i] != sir2[k] && i > 0)
            i = v[i-1];
        if(i == 0 && sir1[i] != sir2[k])
            k++;
    }
    cout << cnt << '\n';
    for(int i = 1; i <= cnt; i++)
        cout << poz[i]<<' ';
    return 0;
}