Cod sursa(job #2344758)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 15 februarie 2019 16:25:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 2000003;

void piFunction(const string &pattern, int pi[]){
    pi[0] = -1;
    for(int i = 1; i < pattern.size(); ++i){
        int k = pi[i - 1];
        while(pattern[k + 1] != pattern[i]){
            if(k == -1)
                break;
            k = pi[k];
        }
        if(pattern[k + 1] != pattern[i]){
            pi[i] = -1;
        }else{
            pi[i] = k + 1;
        }
    }
}
void KMP(const string &pattern, const string &text, int pi[]){
    piFunction(pattern, pi);
    int k = -1;
    int *piText;
    int n = 0;
    vector<int> ans;
    piText = new int[NMax];
    memset(piText, 0, sizeof(piText));
    for(int i = 0; i < text.size(); ++i){
        if(i == 0){
            k = -1;
        }else{
            k = piText[i - 1];
        }
        while(pattern[k + 1] != text[i]){
            if(k == -1)
                break;
            k = pi[k];
        }
        if(pattern[k + 1] != text[i]){
            piText[i] = -1;
        }else{
            piText[i] = k + 1;
            if(piText[i] == pattern.size() - 1){
                n++;
                if(n <= 1000){
                    ans.push_back(i - pattern.size() + 1);
                }
            }
        }
    }
    outFile << n << '\n';
    for(int i = 0; i < ans.size(); ++i){
        outFile << ans[i] << ' ';
    }
}
int main(){
    string pattern,text;
    int *pi;
    pi = new int[NMax];
    inFile >> pattern;
    inFile >> text;
    KMP(pattern, text, pi);
    return 0;
}