圖論 弦

Problem statement:

問題陳述：

You are provided an input string S and the string "includehelp". You need to figure out all possible subsequences "includehelp" in the string S? Find out the number of ways in which the subsequence "includehelp" can be formed from the string S.

將為您提供輸入字符串S和字符串“ includehelp”。 您需要找出字符串S中所有可能的子序列“ includehelp”。 找出從字符串S形成子序列“ includehelp”的方式的數量。

Input:

輸入：

Input is the string s

輸入是字符串s

Output:

輸出：

Corresponding to each test case, print in a new line, a number denoting the number of ways in which we can form the subsequence "includehelp". Since output can be very large find the answer modulo 1000000007.

對應于每個測試用例，在新行中打印，該數字表示我們形成子序列“ includehelp”的方式的數量。 由于輸出可能非常大，因此請找到模1000000007的答案。

Constraints:

限制條件：

Input String contains only lowercase English Letters and string length is 5000 at maximum.

輸入字符串僅包含小寫英文字母，并且字符串長度最大為5000。

Example:

例：

Input:
includehelp
Output:
1
Explanation:
There is only one instances of "includehelp" 
in the above input string.
Input:
iincludehelp
Output:
2
Explanation:
There is two instances of "includehelp" 
in the above input string.

Solution Approach:

解決方法：

Let the input string be, s and t="includehelp"
This problem can be solved by recursion.
So we have,
string s: the input string
string t: the second string ("includehelp")
starts  : start point of string s
srartt  : start point of string t, ("includehelp")
m: length of input string
11: length of string t,"includehelp"
MOD: 1000000009

Now, how can we generate a recursive relation?

現在，我們如何生成遞歸關系？

Say starts=i where 0<=i<m & startt=j where 0<=j<11

說starts = i ，其中0 <= i <m＆startt = j ，其中0 <= j <11

Say,

說，

1. s[starts]=t[startt] that means both have same character,

   s [starts] = t [startt]表示兩個字符相同，

   Now we have two options,

   現在我們有兩個選擇，

   1. starts+1, starts + 1 ， startt+1 which means we are looking for the same occurrence, we want to check for other characters as well.startt + 1 ，這意味著我們正在尋找相同的事件，我們也想檢查其他字符。
   2. starts+1, starts + 1和startt which means we are looking for another different occurrence.startt ，這意味著我們正在尋找另一個不同的事件。

2. s[starts]!=t[startt]

   s [starts]！= t [startt]

   Now we have only one option which is check for

   現在我們只有一個選項可以檢查

   starts+1, startt as we need to look for different occurrence only.

   starts + 1 ， startt，因為我們只需要查找不同的事件。

Function:
jumbleString(string s,string t,int starts,int startt,int m)
// enter substring is matched
if startt==11
return 1;
// enter string has been searched with out match 
if starts==m
return 0;
if(s[starts]!=t[startt])
//only one option as we discussed
return jumbleString(s,t,starts+1,startt,m)%MOD;
else
// both the options as we discussed
return (jumbleString(s,t,starts+1,startt+1,m)%MOD +
jumbleString(s,t,starts+1,startt,m)%MOD)%MOD

The above recursion will generate many overlapping subproblems and hence we need to use dynamic programming.

上面的遞歸將產生許多重疊的子問題，因此我們需要使用動態編程。

Let's convert the recursion to DP.

讓我們將遞歸轉換為DP。

• Step 1: initialize DP table,

  步驟1：初始化DP表，

  int dp[m+1][12];
  
  

• Step 2: convert step1 of recursive function,

  步驟2：轉換遞歸函數的step1，

  for i=0 to 11
  dp[0][i]=0;
  
  

• Step 3: convert step 2 of recursive function,

  步驟3：轉換遞歸函數的步驟2，

  for i=0 to m
  dp[i][0]=1;
  
  

• Step 4: Fill the DP table which is similar to step3 of the recursion function,

  步驟4：填寫DP表，該表類似于遞歸函數的步驟3，

  for i=1 to m
  for j=1 to 11
  if s[i-1]==t[j-1]
  dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MOD
  else
  dp[i][j]=dp[i-1][j]
  end for
  end for
  
  

• Step5: return dp[m][11] which is the result.

  步驟5：返回結果dp [m] [11] 。

The above DP technique is known as the tabulation process. We can introduce memorization as well, known as the top-down approach. Where we store every computed subproblem and while computing first we look up our DP table whether sub-problem is already solved or not. Check the below top-down implementation for the above problem.

上述DP技術稱為制表過程。 我們也可以引入記憶，稱為自頂向下方法。 我們存儲每個計算出的子問題的位置，并且在進行第一次計算時，無論子問題是否已解決，我們都會查看DP表。 檢查以下自上而下的實現是否存在上述問題。

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int dp[1001][12];
int jumbled(string s1, string s2, int i, int j, int n, int m)
{
if (j == m) {
return 1;
}
if (i == n && j != m)
return 0;
// if subproblem already solved
if (dp[i][j] != -1) 
return dp[i][j];
if (s1[i] == s2[j]) {
dp[i][j] = jumbled(s1, s2, i + 1, j + 1, n, m) + jumbled(s1, s2, i + 1, j, n, m);
}
else {
dp[i][j] = jumbled(s1, s2, i + 1, j, n, m);
}
return dp[i][j];
}
int main()
{
int n;
string s2 = "includehelp";
string s1;
cout << "Input string: ";
cin >> s1;
n = s1.length();
for (int i = 0; i < n; i++) {
for (int j = 0; j < 11; j++)
dp[i][j] = -1;
}
cout << "We can jumble " << jumbled(s1, s2, 0, 0, n, 11) << " of ways." << endl;
return 0;
}

Output:

輸出：

Input string: iincludehelp
We can jumble 2 of ways.

翻譯自: https://www.includehelp.com/icp/jumbled-strings.aspx

圖論 弦