Problem Statement

Given two strings s and t, and an integer k, determine if it's possible to extract two non-overlapping substrings of length k from s such that when concatenated, the resulting string contians t as a contiguous substring.

Approach

1. Problem Analysis: The solution involves checking if t can be formed by combining parts of two non-overlapping k-length substrings from s. The challenge is to efficiently find these substrings without resorting to an O(n*m) brute-force approach.

2. Key Insight:

   • Precompute the earliest starting position in s for every prefix of t (up to length k).
   • Precompute the latest starting position in s for every suffix of t (up to length k).
   • Use rolling hashes to efficiently compare substrings.

3. Algorithm Selection:

   • Prefix Matching: For each prefix length i (1 to min(m, k)), find the first occurrence in s ending at or before position k. If not found, extend the search rightwards.
   • Suffix Matching: Similarly, for each suffix length i, find the last occurrence in s starting at or after position n-k+1. If not found, extend the search leftwards.
   • Check Conditions: For each possible split point in t (from 1 to m-1), verify if the prefix and suffix can be covered by the two substrings without overlapping.
   • Edge Case Handling: If t is entirely contained within one of the k-length substrings, directly return valid positions.

Solution Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int MAX = 500010;
const unsigned long long BASE = 233;

unsigned long long base_pow[MAX];
unsigned long long s_hash[MAX], t_hash[MAX];

inline unsigned long long get_substr_hash(unsigned long long *hash_arr, int l, int r) {
    return hash_arr[r] - hash_arr[l-1] * base_pow[r - l + 1];
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    if (n < 2*k || m > 2*k) {
        cout << "No" << endl;
        return 0;
    }
    
    string s_str, t_str;
    cin >> s_str >> t_str;
    s_str = " " + s_str;
    t_str = " " + t_str;
    
    base_pow[0] = 1;
    for (int i = 1; i <= n; i++) {
        base_pow[i] = base_pow[i-1] * BASE;
    }
    
    for (int i = 1; i <= n; i++) {
        s_hash[i] = s_hash[i-1] * BASE + (s_str[i] - 'a' + 1);
    }
    for (int i = 1; i <= m; i++) {
        t_hash[i] = t_hash[i-1] * BASE + (t_str[i] - 'a' + 1);
    }
    
    vector<int> prefix_min(m+1, n+1);
    vector<int> suffix_max(m+2, 0);
    
    int ptr = k;
    for (int len = 1; len <= min(m, k); len++) {
        unsigned long long target = t_hash[len];
        while (ptr <= n) {
            int start = ptr - len + 1;
            if (start < 1) {
                ptr++;
                continue;
            }
            if (get_substr_hash(s_hash, start, ptr) == target) {
                break;
            }
            ptr++;
        }
        if (get_substr_hash(s_hash, k - len + 1, k) == target) {
            ptr = k;
        }
        prefix_min[len] = ptr;
    }
    
    ptr = n - k + 1;
    for (int suffix_len = 1; suffix_len <= min(m, k); suffix_len++) {
        int t_start = m - suffix_len + 1;
        unsigned long long target = get_substr_hash(t_hash, t_start, m);
        while (ptr >= 1) {
            if (get_substr_hash(s_hash, ptr, ptr + suffix_len - 1) == target) {
                break;
            }
            ptr--;
        }
        if (get_substr_hash(s_hash, n - k + 1, n - k + suffix_len) == target) {
            ptr = n - k + 1;
        }
        suffix_max[t_start] = ptr;
    }
    
    int ans1 = 0, ans2 = 0;
    for (int split = 1; split < m; split++) {
        if (split > k || m - split > k) continue;
        int prefix_end = prefix_min[split];
        int suffix_start = suffix_max[split+1];
        if (prefix_end <= n && suffix_start >= 1 && suffix_start > prefix_end) {
            ans1 = prefix_end - k + 1;
            ans2 = suffix_start;
            cout << "Yes" << endl;
            cout << ans1 << " " << ans2 << endl;
            return 0;
        }
    }
    
    if (k >= m) {
        for (int start = 1; start <= k; start++) {
            if (start + m - 1 > n) break;
            if (get_substr_hash(s_hash, start, start + m - 1) == t_hash[m]) {
                cout << "Yes" << endl;
                cout << 1 << " " << k+1 << endl;
                return 0;
            }
        }
        for (int start = n - k + 1; start <= n; start++) {
            if (start + m - 1 > n) break;
            if (get_substr_hash(s_hash, start, start + m - 1) == t_hash[m]) {
                cout << "Yes" << endl;
                cout << n - 2*k + 1 << " " << n - k + 1 << endl;
                return 0;
            }
        }
    }
    
    cout << "No" << endl;
    return 0;
}

Explanation

1. Initialization: The code starts by validating input constraints (if s is too short or t too long).
2. Hashing Setup: Precomputes base powers for rolling hash and computes hash arrays for both strings.
3. Prefix and Suffix Arrays:
   • prefix_min[i] stores earliest position in s where the prefix of t of length i ends.
   • suffix_max[i] stores the latest position in s where the suffix of t starting at i begins.
4. Matching Check: For each possible split of t into a prefix and suffix, checks if there exist non-overlapping substrings in s covering both parts.
5. Edge Handling: If t fits entirely with in a single k-length substring, checks the first and last possible positions in s.
6. Output: If valid positions are found, outputs "Yes" and the positions; otherwise, outputs "No".