字符串查找字符出现次数
Description:
描述：
It's a popular interview question based of dynamic programming which has been already featured in Accolite, Amazon.
这是一个流行的基于动态编程的面试问题，已经在亚马逊的Accolite中得到了体现。
Problem statement:
问题陈述：
Given two stringsSandT, find the number of times the second string occurs in the first string, whether continuous or discontinuous as subsequence.
给定两个字符串S和T，找出第二个字符串在第一个字符串中出现的次数，无论是连续的还是不连续的作为子序列。
Input:String S: "iloveincludehelp"String T: "il"Output:5
Explanation:
说明：
The first string is,
第一个字符串是
The second string is "il"
第二个字符串是“ il”
First occurrence:
第一次出现：
Second occurrence:
第二次出现：
Third occurrence:
第三次出现：
Fouth occurrence:
发生口：
Fifth occurrence:
第五次出现：
So, total distinct occurrences are 5.
因此，总的不重复发生次数为5。
Solution Approach:
解决方法：
First, we discuss the recursive solution and then we will convert it to dynamic programming.
首先，我们讨论递归解决方案，然后将其转换为动态编程。
Prerequisite:
先决条件：
string s: the first stringstring t: the second stringstarts: start point of the first stringsrartt: start point of the second stringm : length of first stringn : length of second string
How, how can we generate a recursive relation?
如何，如何生成递归关系？
Say,
说，
starts=i where i<m and i>=0 & start=j where j<n and j>=0
Say,
说，
s[starts] = t[start] that means both have same character,
s [starts] = t [start]表示两个字符相同，
Now we have to option,
现在我们必须选择
Check for starts+1, startt+1 which means we are looking for the same occurrence, we want to check for other characters as well. 检查starts + 1 ， startt + 1 ，这意味着我们正在寻找相同的事件，我们也想检查其他字符。 Check for starts+1, startt which means we are looking for another different occurrence. 检查starts + 1和startt ，这意味着我们正在寻找另一个不同的事件。
s[starts] != t[start]
s [开始]！= t [开始]
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 distinctOccurence(string s,string t,int starts,int startt,int m,int n)if startt==n //enter substring is matchedreturn 1;if starts==m //enter string has been searched with out match return 0;if(s[starts]!=t[startt])//only one option as we discussedreturn distinctOccurence(s,t,starts+1,startt,m,n); else//both the options as we discussedreturn distinctOccurence(s,t,starts+1,startt+1,m,n) + distinctOccurence(s,t,starts+1,startt,m,n);
The above recursion will generate many overlapping subproblems and hence we need to use dynamic programming. (I would recommend to take two short string and try doing by your hand and draw the recursion tree to understand how recursion is working).
上面的递归将产生许多重叠的子问题，因此我们需要使用动态编程。 (我建议您取两个短字符串，然后用手尝试画出递归树，以了解递归的工作方式)。
Let's convert the recursion to DP.
让我们将递归转换为DP。
Step1: initialize DP tableint dp[m+1][n+1];Step2: convert step1 of recursive functionfor i=0 to ndp[0][i]=0;Step3: convert step2 of recursive functionfor i=0 to mdp[i][0]=1;Step4: Fill the DP table which is similar to step3 of the recursion functionfor i=1 to mfor j=1 to nif s[i-1]==t[j-1]dp[i][j]=dp[i-1][j]+dp[i-1][j-1]elsedp[i][j]=dp[i-1][j]end forend forStep5: return dp[m][n] which is the result.
C++ Implementation:
C ++实现：
#include <bits/stdc++.h>using namespace std;int distinctOccurence(string s, string t, int starts, int startt, int m, int n) {//note argument k,l are of no use here//initialize dp tableint dp[m + 1][n + 1];//base casesfor (int i = 0; i <= n; i++)dp[0][i] = 0;for (int i = 0; i <= m; i++)dp[i][0] = 1;//fill the dp tablefor (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s[i - 1] == t[j - 1])dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];elsedp[i][j] = dp[i - 1][j];}}return dp[m][n];}int main() {int n, m;string s1, s2;cout << "Enter the main string:\n";cin >> s1;cout << "Enter the substring:\n";cin >> s2;m = s1.length();n = s2.length();cout << s2 << " has " << distinctOccurence(s1, s2, 0, 0, m, n) << " times different occurences in " << s1 << endl;return 0;}
Output
输出量
Enter the main string:iloveincludehelpEnter the substring:ilil has 5 times different occurences in iloveincludehelp
翻译自: /icp/find-number-of-times-a-string-occurs-as-a-subsequence.aspx
字符串查找字符出现次数
