Cod sursa(job #2736486)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 3 aprilie 2021 15:27:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char a[2000001];
char b[2000001];
int suff[2000001];
int sol[1024];
void build (int m)
{
    int n=0;
    int i;
    suff[0]=0;
    for (i=1;i<m;i++){
        if (a[i]==a[n]){
            n++;
            suff[i]=n;
        }
        else{
            if (n){
                n=suff[n-1];
                i--;
            }
            else{
                suff[i]=0;
            }
        }
    }
}

int main()
{
    cin>>a;
    cin>>b;
    int s=0;
    int m=strlen(a);
    int n=strlen(b);
    build(m);
    int i=0,j=0;
    while(i<n){
        if (a[j]==b[i]){
            i++;
            j++;
        }
        if (j==m){
            if (s<1000) sol[s]=i-j,s++;
            j=suff[j-1];
        }
        else {
            if (i<n && a[j]!=b[i]){
                if (j) j=suff[j-1];
                else i++;
            }
        }
    }
    cout<<s<<"\n";
    for (i=0;i<s;i++){
        cout<<sol[i]<<" ";
    }
    return 0;
}