Cod sursa(job #3175743)

Utilizator paull122Paul Ion paull122 Data 26 noiembrie 2023 13:16:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
#define MOD 666013


ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int pi[2000001];
char a[2000001];
char b[2000001];
int main()
{
    fin >> a >> b;
    pi[0]=0;
    int len=0;
    int i=1;
    while(i < strlen(a))
    {
        if(a[i]==a[len])
        {
            len++;
            pi[i]=len;
            i++;
        }
        else
        {
            if(len !=0)
            {
                len = pi[len-1];
            }
            else
            {
                pi[i]=0;
                i++;
            }
        }
    }
    vector<int> r;
    i=0;
    int j=0;
    while(i<strlen(b))
    {
        if(a[j]==b[i])
        {
            j++;
            i++;
        }
        if(j==strlen(a))
        {
            r.push_back(i-j);
            j=pi[j-1];
        }
        else if(i < strlen(b) && a[j]!=b[i])
        {
            if(j!=0)
            {
                j = pi[j-1];
            }
            else
            {
                i++;
            }
        }
    }
    fout << r.size() << "\n";
    for(int i : r)fout << i << " ";
}