Cod sursa(job #2542003)

Utilizator DanilaAlexandraDanila Mihaela-Alexandra DanilaAlexandra Data 9 februarie 2020 12:24:43
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

int n,m;
int rez[100];
int w=0;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    int urm[200000];
    int k,q;
    char p[200000],t[200000];
    f.getline(p,100);
    n=strlen(p);
    f.getline(t,100);
    m=strlen(t);
    urm[0]=-1;
    k=-1;
    for(int q=1;q<n;q++){
        while(k>=0&&p[k+1]!=p[q]) k=urm[k];
        if(p[k+1]==p[q]) k++;
        urm[q]=k;
    }
    k=-1;
    for(int q=0;q<m;q++){
        while(k>=0&&p[k+1]!=t[q]) k=urm[k];
        if(p[k+1]==t[q]) k++;
        if(k==n-1){
            rez[w++]=q-k;
            k=urm[k];
        }
    }
    g<<w<<'\n';
    for(int i=0;i<w;i++) g<<rez[i]<<" ";
    return 0;
}