Cod sursa(job #2097179)

Utilizator mihailrazMihail Turcan mihailraz Data 30 decembrie 2017 17:48:03
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
#define MAX 2000000

using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char A[MAX+5],B[MAX+5];
int n,m;
int LPS[MAX+5];
vector <int> V;

void citire(void)
{
    fi>>A;
    fi>>B;
    n=strlen(B);
    m=strlen(A);
}

void generare_lps(char P[])
{
    /// calculeaza lungimile prefixelor care sunt si sufixe
    LPS[0]=0;
//    for(int i=1,j=0; i<m; i++)
//    {
//        if(P[i]==P[j])
//        {
//            LPS[i]=j+1;
//            //i++;
//            j++;
//        }
//        else
//        {
//            if(j==0)
//            {
//                LPS[i]=0;
//                //i++;
//            }
//            else
//                j=LPS[j-1];
//                LPS[i] = j;
//        }
//    }
    int j=0;
    for(int i=1; i<m; i++)
    {
        while(j&&P[j+1]!=P[i])
            j=LPS[j];
        if(P[j+1]==P[i])
            j++;
            LPS[i]=j;

    }
}

void KMP(char T[], char P[])
{
    for(int i=0,j=0; i<n;)
    {
        if(T[i]==P[j])
        {
            i++;
            j++;
        }
        if(j==m)
        {
            if(V.size()<1000)
                V.push_back(i-m);
            j=LPS[j-1];
        }
        if(i<n && T[i]!=P[j])
        {
            if(j!=0)
                j=LPS[j-1];
            else
                i++;
        }
    }
}

void afisare(void)
{
    fo<<V.size()<<"\n";
    for(int i=0; i<V.size(); i++)
        fo<<V[i]<<" ";
}

int main()
{
    citire();
    generare_lps(A);
    KMP(B,A);
    afisare();
    fi.close();
    fo.close();
    return 0;
}