Cod sursa(job #2173459)

Utilizator AlexTudorAlex Brinza AlexTudor Data 15 martie 2018 22:21:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define N 2000000
using namespace std;

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

char T[N],P[N];
int L[N],d[N];
int n,m;
int poz[2000000];


void precalc()
{
    int i,k=0;
    L[0]=0;
    for(i=1;i<m;++i)
    {
        if(P[i]==P[k]) k++;
        else
            {while(k>0 && P[i]!=P[k]) k=L[k-1];
             if(P[i]==P[k]) k++;
            }
        L[i]=k;
    }
}

void kmp()
{
    int i,k=0;
    for(i=0;i<n;++i)
    {
        if(T[i]==P[k]) k++;
        else
            {while(k>0 && T[i]!=P[k]) k=L[k-1];
             if(T[i]==P[k]) k++;
            }
        d[i]=k;
    }
}


int main()
{
    fin>>P>>T;
    n=strlen(T);
    m=strlen(P);
    precalc();
    int i;
    int ct=0;
    kmp();
    for(i=0;i<n;++i)
        if(d[i]==m)
          {
             ct++;
             poz[ct]=i-m+1;
            }
    fout<<ct<<"\n";
    for(i=1;i<=ct;++i) fout<<poz[i]<<" ";
    return 0;
}