Cod sursa(job #2498239)

Utilizator Bogdan_BuzatuBuzatu Bogdan Mihai Bogdan_Buzatu Data 23 noiembrie 2019 17:39:17
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
// C++ program for implementation of KMP pattern searching
// algorithm
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int sol[100000],cont;
char a[2000010], b[2000010];
void PAS(char* sir1, int M, int* lps);
void KMP(char* sir1, char* sir2,int &cont,int sol[]){
    int m=strlen(sir1);
    int n=strlen(sir2);

    int lps[m];

    PAS(sir1, m, lps);

    int i = 0;
    int j = 0;
    while (i<n) {
        if (sir1[j] == sir2[i]) {
            j++;
            i++;
        }

        if (j == m) {
            cont++;
            sol[cont]=i-j;
            j=lps[j-1];
        }
        else{
            if(i<n&& sir1[j] != sir2[i]) {
                if (j != 0){
                    j = lps[j - 1];
                }
                else{
                    i = i + 1;
                }

            }
        }
    }
}

void PAS(char* sir1, int M, int* lps){
    int len = 0;

    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (sir1[i] == sir1[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else{
            if (len != 0) {
                len = lps[len - 1];
            }
            else{
                lps[i] = 0;
                i++;
            }
        }
    }
}

// Driver program to test above function
int main(){
    fin>>a;
    fin>>b;
    KMP(a, b,cont,sol);

    fout<<cont<<"\n";
    for(int i=1;i<=min(cont,1000);i++){
        fout<<sol[i]<<" ";
    }
    return 0;
}