Cod sursa(job #2724241)

Utilizator handicapatucavasi eduard handicapatu Data 16 martie 2021 19:41:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string pattern,text;
int n,m;
int ans[2000001];
int lps[2000001];
void compute_lps_array(){
    int len = 0;
    lps[len] = 0;
    int i = 1;
    while(i <= n){
        if(pattern[i] == pattern[len]){
            ++len;
            lps[i] = len;
            ++i;
        }
        else{
            if(len != 0){
                len = lps[len-1];
            }
            else{
                lps[i] = 0;
                ++i;
            }
        }
    }
}
void kmp(){
    int nr = 0;
    int i = 0 , j = 0;
    compute_lps_array();
    while (i < m){
        if(pattern[j] == text[i]){
            ++i;
            ++j;
        }
        if(j==n){
            ++nr;
            ans[nr] = i-j;
            j = lps[j-1];
        }
        else if(i < m && pattern[j] != text[i]){
            if(j != 0){
                j = lps[j-1];
            }
            else{
                ++i;
            }
        }
    }
    g<<nr<<endl;
    for(int k=1;k<=min(nr,1000);++k){
        g<<ans[k]<<" ";
    }
}
int main()
{
    f>>pattern>>text;
    n = pattern.length();
    m = text.length();
    kmp();
    return 0;
}