C ++で2番目の文字列に対してスワップを実行した後、2つの文字列間の最長の共通プレフィックスを検索します

2つの文字列str1とstr2があるとします。 2番目の文字列に対してゼロ以上の操作を実行した後、それらの間で最も長い共通プレフィックスを見つけます。各操作で、任意の2文字を入れ替えることができます。したがって、str1 =“ HERE”、str2 =“ THERE”の場合、出力は4になります。2番目の文字列は、文字を入れ替えるだけで“ HERET”にすることができます。したがって、最長のプレフィックスの長さは4です。

私たちが知っているように、私たちはstr2でしか交換できません。また、マトリックスの長さを最大化する必要があります。したがって、str1をトラバースし、str1の現在の文字の頻度がstr2の頻度と同じかそれ以下かどうかを確認するという考え方です。はいの場合は、文字列aで前方に移動します。そうでない場合は、文字列str1で文字が一致する部分の長さを分割して、文字列str2で出力します。

例

#include <iostream>
using namespace std;
void longestPrefix(string str1, string str2) {
   int frequency[26]={0};
   int a = str1.length();
   int b = str2.length();
   for (int i=0 ;i<b ; i++) {
      frequency[str2[i] - 97] += 1;
   }
   int c = 0;
   for (int i=0 ;i<a ; i++) {
      if (frequency[str1[i] - 97] > 0){
         c += 1;
         frequency[str1[i] - 97] -= 1;
      } else
      break;
   }
   cout<<"Length of longest common prefix: " << c;
}
int main() {
   string str1="here", str2 = "there";
   longestPrefix(str1, str2);
}

出力

Length of longest common prefix: 4