Cod sursa(job #2239853)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 11 septembrie 2018 22:26:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>

const int MAXN = 2000005;

using namespace std;

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

int lps[MAXN],n,m;//Longest prefix and suffix of pattern [0...i] #geeksforgeeks
string text,pattern;
vector<int>ans;

void LPS_generator(){
    int i = 1,j = 0;
    while(i < m){
        if(pattern[i] == pattern[j]){
            j++;
            lps[i] = j;
            i++;
        }else{
            if(j)
                j = lps[j - 1];
            else{
                lps[i] = 0;
                i++;
            }
        }
    }

}
void KMP(){
    int i = 0,j = 0;

    while(i < n){
        if(text[i] == pattern[j]){
            j++;
            i++;
            if(j == m){
                ans.push_back(i - j);
                j = lps[j - 1];
            }
        }else{
            if(j)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

int main()
{
    in>>pattern>>text;
    n = text.size(),m = pattern.size();

    LPS_generator();
    KMP();

    out<<ans.size()<<"\n";
    for(int i = 0; i < ans.size() && i < 1000; i++)
        out<<ans[i]<<" ";

    return 0;
}