Cod sursa(job #1832391)

Utilizator trettdragosTrett Dragos trettdragos Data 19 decembrie 2016 21:57:51
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char s[200001], a[200001];
int n, m;

int fix(int k){
    int aux[200001]={0};
    int j=0, i=1;
    while(i<=k){
        if(a[i]==a[j]){
            aux[i]=j+1;
            j++;
        }
        else{
            while(j>0){
                j=aux[j-1];
                if(a[i]==a[j]){
                    aux[i]=j+1;
                    j++;
                    break;
                }
            }
        }
        i++;
    }
    return aux[n-1];
}

int kjh[1000];
int k=0;
int kmp(){
    int nr=0;
    int i=0, j=0, ok=0;
    while(i<m)
    {
        if(a[j]==s[i])
        {
            j++;
            ok=1;
        }
        else if(ok==1){
            j=fix(j-1);
            ok=0;
        }
        if(j==n && ok==1 && nr<=1000)
            {nr++;
            kjh[k++]=i-n+1;
            j=fix(j-1);
            ok=0;}
        i++;
    }
    return nr;
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin.getline(a, 200001);
    cin.getline(s, 200001);
    n=strlen(a);
    m=strlen(s);
    cout<<kmp()<<endl;
    for(int i=0; i<k; i++)
        cout<<kjh[i]<<" ";
    return 0;
}