Cod sursa(job #2187247)

Utilizator mariastStoichitescu Maria mariast Data 26 martie 2018 12:29:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int pi[2000006],sol[2000],k,x;
char A[2000006],B[2000006];
int main()
{
    f.getline(A+1,2000006);
    f.getline(B+1,2000006);
    pi[1]=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;
        if(k==n){
            x++;
            k=pi[k];
            if(x<=1000) sol[x]=i-n;
        }
    }
    g<<x<<'\n';
    for(int i=1;i<=x;++i){
        g<<sol[i]<<' ';
        if(i==1000) return 0;
    }
    return 0;
}