Cod sursa(job #2187227)

Utilizator mariastStoichitescu Maria mariast Data 26 martie 2018 12:21:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int pi[200006],d[200006],k,x;
char A[200006],B[200006];
int main()
{
    f.getline(A+1, 2000006);
    f.getline(B+1, 2000006);
    pi[1]=0;
    A[0]=B[0]=' ';
    int n=strlen(A)-1;
    int m=strlen(B)-1;
    k=0;
    for(int i=2;i<=n;++i){
        while(k&&A[i]!=A[k+1]) k=pi[k];
        if(A[k+1]==A[i]) ++k;
        pi[i]=k;
    }
    k=0;
    for(int i=1;i<=m;++i){
        while(k&&B[i]!=A[k+1]) k=pi[k];
        if(B[i]==A[k+1]) ++k;
        d[i]=k;
        if(d[i]==n) x++;
    }
    g<<x<<'\n';
    int nr=0;
    for(int i=1;i<=m;++i){
        if(d[i]==n){
            g<<i-n<<" ";
            nr++;
            if(nr==x||nr==1000) return 0;
        }
    }
    return 0;
}