Cod sursa(job #2263598)

Utilizator TeoDiDiaconescu Teodora TeoDi Data 18 octombrie 2018 21:02:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <string.h>
#define nMax 2000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int Urm[nMax];
char T[nMax],P[nMax];
int n,m;
int ct,j[1001];
void Urmatorul(char *P)
{
    int k=-1,x;
    Urm[0]=0;
    for(x=1;x<m;x++)
    {
        while(k>0 && P[k+1]!=P[x]) k=Urm[k];
        if(P[k+1]==P[x]) k++;
        Urm[x]=k;
    }
}
int main()
{
    int i,x=-1; f.getline(P,2000000); f.getline(T,2000000);
    n=strlen(T); m=strlen(P);
    Urmatorul(P);
    for(i=0;i<n;i++)
    {
        while(x>0 && P[x+1]!=T[i]) x=Urm[x];
        if(P[x+1]==T[i]) x++;
        if(x==m-1 && ct<=1000)
        {
            ct++;
            j[ct]=i-m+1;
            x=Urm[x];
        }
    }
    g<<ct<<'\n';
    for(int i=1;i<=ct;i++) g<<j[i]<<' ';
    return 0;
}