Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
3.6 kB
1
Indexable
Never
#include <algorithm>
#include <ios>
#include <iostream>
#include <string>
#include <vector>



int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

    // char ch;
    // std::string str;
    // str.reserve(2000001);

    // size_t psize = 0;

    // while (std::cin.get(ch)) {
    //     if (ch == '\n') {
    //         str.push_back('#');
    //         break;
    //     }

    //     str.push_back(ch);
    //     ++psize;
    // }

    // std::string reverse_str;
    // reverse_str.reserve(2000001);
    // int index = psize - 1;
    // size_t tsize = 0;

    // while (std::cin.get(ch)) {
    //     if (index >= 0) {
    //         reverse_str.push_back(str[index]);
    //         --index;
    //     }

    //     if (ch == '\n') {
    //         break;
    //     }

    //     str.push_back(ch);
    //     ++tsize;
    // }

    // index = str.size() - 1;
    // reverse_str.push_back('#');

    // while (index > psize) {
    //     reverse_str.push_back(str[index]);
    //     --index;
    // }


    std::string p;
    p.reserve(1000001);
    std::getline(std::cin, p);

    //int psize = p.size();

    std::string str;
    str.reserve(2000003);

    std::string reverse_str;
    reverse_str.reserve(2000003);

    str.append(p);
    str.push_back('#');

    std::reverse(p.begin(), p.end());
    reverse_str.append(p);
    reverse_str.push_back('#');

    std::getline(std::cin, p);

    //int tsize = p.size();
    str.append(p);

    std::reverse(p.begin(), p.end());
    reverse_str.append(p);


    // // std::string t = "Caaabdaaaa";
    // // std::string p = "aaaa";


    std::vector<int> prefix(str.size(), 0);
    std::vector<int> suffix(reverse_str.size(), 0);
    int left = 0;
    int right = 0;
    int reverse_left = 0;
    int reverse_right = 0;


    for (int i = 1; i < str.size(); ++i) {
        if (i <= right) {
            prefix[i] = std::min(right - i + 1, prefix[i - left]);
        }

        while (i + prefix[i] < str.size() && str[prefix[i]] == str[i + prefix[i]]) {
            ++prefix[i];
        }

        if (i + prefix[i] - 1 > right) {
            right = i + prefix[i] - 1;
            left = i;
        }


        if (i <= reverse_right) {
            suffix[i] = std::min(reverse_right - i + 1, suffix[i - reverse_left]);
        }

        while (i + suffix[i] < reverse_str.size() && reverse_str[suffix[i]] == reverse_str[i + suffix[i]]) {
            ++suffix[i];
        }

        if (i + suffix[i] - 1 > reverse_right) {
            reverse_right = i + suffix[i] - 1;
            reverse_left = i;
        }
    }


    // for (int i = 0; i < prefix.size(); ++i) {
    //     std::cout << prefix[i] << " ";
    // }
    // std::cout << "\n";

    // for (int i = 0; i < suffix.size(); ++i) {
    //     std::cout << suffix[i] << " ";
    // }
    // std::cout << "\n";

    std::cout << 0;
    return 0;

    // int count = 0;
    // std::vector<int> data;
    // data.reserve(tsize - psize);

    // int min_size = psize - 1;

    // for (int i = psize + 1, end = prefix.size() - psize; i <= end; ++i) {
    //     int skip_index = str.size() - i + prefix[i] + 1;

    //     if (prefix[i] == psize || prefix[i] == min_size
    //         || (skip_index < suffix.size() && prefix[i] + suffix[skip_index] == min_size)) {
    //         data.emplace_back(i - psize);
    //         ++count;
    //     }
    // }
    
    // std::cout << count << "\n";
    // for (const auto& pos : data) {
    //     std::cout << pos << " ";
    // }
    // std::cout << "\n";


    return 0;
}
Leave a Comment