Cod sursa(job #1562666)

Utilizator rares00Foica Rares rares00 Data 5 ianuarie 2016 13:09:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

char A[2000001];
char B[2000001];
int pi[2000001];
int poz[1001],nrpoz;
int lenA,lenB;

void genPI()
{
    int k=0;
    pi[0]=0;
    for(int i=1;i<=lenA-1;i++)
    {
        while(k>0 && A[i]!=A[k])
            k=pi[k-1];

        if(A[k]==A[i])
            k++;

        pi[i]=k;
    }
}

int main()
{
    int k;
    in>>A>>B;
    lenA=strlen(A);
    lenB=strlen(B);

    genPI();
    //for(int i=0;i<=lenA-1;i++) out<<pi[i]<<" ";
    k=0;
    for(int i=0;i<=lenB-1;i++)
    {
        while(k>0 && B[i]!=A[k])
            k=pi[k-1];

        if(A[k]==B[i])
            k++;

        if(k==lenA)
        {
            nrpoz++;
            if(nrpoz<=1000)
                poz[nrpoz]=i-lenA+1;
        }
    }

    out<<nrpoz<<"\n";
    if(nrpoz>1000)
        nrpoz=1000;
    for(int i=1;i<=nrpoz;i++)
        out<<poz[i]<<" ";
    return 0;
}