Cod sursa(job #1800219)

Utilizator deliabiancasuciuSuciu delia deliabiancasuciu Data 7 noiembrie 2016 16:06:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char s1[2000005],s2[2000005]; //s1=sirul in care cautam
                              //s2=sirul pe care il cautam
int j,pi[2000005],n,k,i,nr,m,poz[1005];
void prefix()
{
    pi[0]=0; k=0;
    for(i=1;i<=m;i++)
    {
        while(k>0 && s2[i]!=s2[k]) k=pi[k-1];
        if(s2[k]==s2[i]) k++;
        pi[i]=k;
    }
} //formam vectorul de prefixe care sunt si sufixe
int main()
{
    in>>s2>>s1;
    m=strlen(s2)-1; //lungimea sirului model
    n=strlen(s1)-1; //lungimea sirului sursa
    if(m==0){
        for(i=0;i<=n;i++) if(s1[i]==s2[0]){ if(nr<=1000)poz[++nr]=i-m; else nr++;}
    }
    else{
    prefix();
    //for(i=0;i<=m;i++) out<<pi[i]<<" ";
    k=0;
    for(i=0;i<=n-m+2;i++)
    {
        while(k>0&& s2[k]!=s1[i]) k=pi[k-1];
        if(s2[k]==s1[i]) k++;
        if(k==m+1){ if(nr<1000)poz[++nr]=i-m; else nr++;k=pi[k-1];}

    }}
    out<<nr<<"\n";
    for(i=1;i<=nr && i<=1000;i++)
    out<<poz[i]<<" ";
    return 0;
}