Cod sursa(job #3250289)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 19 octombrie 2024 21:22:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int lps[2005], n, m, i, len, j, v[1005], k;
int main()
{
    fin>>a>>b;
    n=a.size();
    m=b.size();
    i=1;
    lps[0]=0;
    while (i<n) {
        if (a[i]==a[len]) {
            len++;
            lps[i]=len;
            i++;
        }
        else {
            if (len==0) {
                lps[i]=len;
                i++;
            }
            else len=lps[len-1];
        }
    }
    for (i=1; i<n; i++) cout<<lps[i]<<' ';
    i=j=0;
    while (i<m) {
        if (j==n) {
            v[++k]=i-n;
            if (k==1000) break;
            j=lps[j-1];
        }
        if (b[i]==a[j]) {
            i++;
            j++;
        }
        else {
            if (j==0) {
                i++;
            }
            j=lps[j-1];
        }
    }
    if (j==n) v[++k]=i-n;
    fout<<k<<'\n';
    for (i=1; i<=k; i++) fout<<v[i]<<' ';
    return 0;
}