Cod sursa(job #1925992)

Utilizator GandalfTheWhiteGandalf the White GandalfTheWhite Data 13 martie 2017 21:28:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000005
using namespace std;

char A[N],B[N];
int lga,lgb,P[N],D[N];
vector <int> Sol;

void Read(){

    freopen("strmatch.in","r",stdin);
    scanf("%s",A+1);
    scanf("%s",B+1);
    A[0]=' ';B[0]=' ';
    lga=strlen(A)-1;lgb=strlen(B)-1;
}

void Prefix(){

    int k=0,i;

    for (i=2;i<=lga;++i){
        while (k && A[i]!=A[k+1]) k=P[k];
        if (A[i]==A[k+1]) k++;
        P[i]=k;
        }
}

void KMP(){

    int k,i;

    Prefix();
    k=0;
    for (i=1;i<=lgb;++i){
        while (k && B[i]!=A[k+1]) k=P[k];
        if (B[i]==A[k+1]) k++;
        if (k==lga) {
            k=P[lga];
            if (Sol.size()<1000) Sol.push_back(i-lga);
            }
        }
}

void Write(){
    int i;
    freopen("strmatch.out","w",stdout);

    printf("%d\n",Sol.size());
    for (int i=0;i<Sol.size();++i)
        printf("%d ",Sol[i]);
}
int main()
{
    Read();
    KMP();
    Write();
    return 0;
}