透過分別連線 N1 次和 N2 次，最大化 S2 作為子序列在 S1 中出現的次數

---

以下文章討論了一種方法，該方法計算在分別連線 N1 次和 N2 次後，字串 s2 在另一個字串 s1 中最大出現次數。這是一個有趣的模式搜尋問題型別。在這篇文章中，我們採用了一種相對直觀的解決方案。

問題陳述

任務是確定字串 s2 在字串 s1 中不重疊出現的最大次數。字串被多次連線：s1 重複 n1 次，s2 重複 n2 次。

示例

輸入

s1 = “abc”, s2 = “ac”, n1 = 4, n2 = 2

輸出

2

解釋

將字串 S1 連線四次後，我們得到字串“abcabcabcabc”。類似地，將字串 S2 連線兩次得到“acac”。透過觀察這一點，我們可以確定字串 S2 在字串 S1 中作為不重疊的子序列出現兩次。因此，期望輸出為 2。

輸入

s1 = “”, s2 = “sfa”, n1 = 7, n2 = 8

輸出

0

解釋

由於 s1 是空字串，在 n1 次自身連線後，它仍然為空。因此，s1 中將不會出現 n2 次連線的 s2。

解決方案方法

一個相當直觀的解決方法是，我們首先分別將字串 s1 和 s2 連線 n1 次和 n2 次。這確保了這些字串足夠長，可以在彼此中找到。然後，我們迭代 s1 中的字元，並檢查它們是否等於 s2 中的相應字元。如果是，我們繼續處理兩個字串中的下一個字元。如果我們到達 s2 的長度，我們增加出現次數計數器。最後，我們返回出現次數計數器。

虛擬碼

• 宣告變數

字串 s1 - 要搜尋的字串

整數 n1 - s1 連線的次數

字串 s2 - 要搜尋的字串

整數 n2 - s2 連線的次數

• 重複 n1 次

將 s1 與 temp 連線

• 重複 n2 次

將 s2 與 temp 連線

• 迭代 s1 中的字元

迭代 s2 中的字元

if current character of string s1 is identical to the current character of string s2,
   Increment j and i
Else,
   Increment i
If j reaches the length of s2,
   Increment the count of occurrences

• 返回出現的次數

示例：C++ 程式

函式 countOccurrence() 統計 s2 在 s1 中出現的次數。n1 和 n2 是 s1 和 s2 連線的次數。該函式首先將 s1 與自身連線 n1 次，將 s2 與自身連線 n2 次。然後，它同時迭代 s1 和 s2，檢查匹配項。如果找到匹配項，則函式會遞增出現計數器。該函式返回計數器的最終值。還有一個條件是 s2 是空字串。程式返回 1，因為空字串作為子序列出現一次。

示例

#include <iostream>
#include <map>
#include <string>
using namespace std;

// The purpose of this function is to determine the count of occurrences of string s2 within string s1.
// The variables n1 and n2 represent the number of times s1 and s2 are concatenated, respectively.
int countOccurrence(string s1, int n1, string s2, int n2){
   string temp = s1;
   while (n1 > 1){
      s1 += temp;
      n1--;
   }
   temp = s2;
   while (n2 > 1){
      s2 += temp;
      n2--;
   }
   int i = 0, j = 0, count = 0;
   while (i < s1.length()){
      j = 0;
      while (j < s2.length() && i < s1.length()){
         // In the event that the current character of s1 matches the current character of s2,
         // increase both j and i by one.
        if (s1[i] == s2[j]){
           j++;
           i++;
        }
        // Else move on to the next character in 's1'
        else{
           i++;
        }
        // If `j` reaches the length of `s2`, increment the count of occurrences.
        if (j == s2.length()){
           count++;
        }
      }
   }
   // Return the count of occurrences.
   return count;
}
int main(){
   string s1 = "abac";
   int n1 = 5;
   cout << "s1: " << s1 << " and n1: " << n1 <<endl;
   string s2 = "a";
   int n2 = 4;
   cout << "s2: " << s2 << " and n2: " << n2 << endl;
   if (s2.length() == 0){
   cout << 1 << endl;
   return 0;
   }
   cout << "count of occurrences of string s2 within string s1: "<< (countOccurrence(s1, n1, s2, n2));
   return 0;
}

輸出

s1: abac and n1: 5
s2: a and n2: 4
count of occurrences of string s2 within string s1: 2

時間和空間複雜度分析

時間複雜度：O(NM)

N 和 M 分別是字串 s1 和 s2 在連線 n1 和 n2 次後的長度。

空間複雜度：O(N)

使用 temp 變數在連線時儲存字串。字串 temp 的長度 = max(length(s1), length(s2))。

結論

本文介紹了一種方法，用於最大化字串 s2 作為子序列在字串 s1 中出現的次數。這是透過將 s1 連線 n1 次和 s2 連線 n2 次實現的。我們藉助合適的示例討論了問題陳述。提供的解決方案方法在 O(NM) 時間內工作，並且相當直觀。可以使用 Boyer Moore 演算法（一種模式搜尋演算法）的變體更有效地解決該問題。