Substring with 1 or 0 mistmatch

search3.cpp

//
// Created by kamenev on 09.03.16.
//

#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>

#define IN "search3"
std::vector<int> z_function(std::string s) {
    int n = (int) s.length();
    std::vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = std::min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

std::vector<int> kmp(std::string P, std::string T) {
    size_t ps = P.size();
    size_t t = T.size();
    std::vector<int> result;
    auto Z1 = z_function(P + "$" + T);
    std::reverse(P.begin(), P.end());
    std::reverse(T.begin(), T.end());
    auto Z2 = z_function(P + "$" + T);
    for (int i = ps+1; i<=Z1.size()-ps; i++) {
        if(Z1[i]>=ps-1) result.push_back(i-ps);
        else if(Z1[i]+Z2[ps+t+1-i+1]>=ps-1) result.push_back(i-ps);
    }
    return result;
}

int main() {
    auto fin = new std::fstream(std::string(IN) + ".in", std::fstream::in);
    auto fout = new std::fstream(std::string(IN) + ".out", std::fstream::out | std::fstream::trunc);
    std::string input, pattern;
    std::getline(*fin, pattern);
    std::getline(*fin, input);
    auto kk = kmp(pattern, input);
    *fout << kk.size() << std::endl;
    std::copy(kk.begin(),kk.end(),std::ostream_iterator<int>(*fout," "));
    delete fin;
    delete fout;
}