「1」で始まり「1」で終わる部分文字列の数をカウントするプログラムをC++で記述します

文字列「str」と文字列の長さを指定したとしましょう。タスクは、特定のバイナリ文字列で「1」で始まり「1」で終わる部分文字列の数をカウントすることです。バイナリ文字列には、「1」と「0」のみが含まれます。たとえば、

入力-1 −

N = 5
str = ‘11101’

出力 −

6

説明 −指定されたバイナリ文字列には、「1」で始まり「1」で終わる6つのサブ文字列があります。これらのサブストリングのセットは、{‘11’、 ‘111’、 ‘1110’、 ‘11101’、 ‘1101’、 ‘101’}です。

入力-1 −

N = 4
str = ‘0011’

出力 −

1

説明 −

指定されたバイナリ文字列には、「1」で始まり「1」で終わる1つのサブ文字列があります。これらのサブストリングのセットは、シングルトンセット、つまり{‘11’}です。

この問題を解決するために使用されるアプローチ

指定された文字列について、「1」で始まり「1」で終わる部分文字列の数を数える必要があります。この問題は、「n」人のパーティーでの握手の数を数える必要がある、よく知られている握手問題に似ています。

指定された文字列の1の数を数えると、「1」で始まり「1」で終わる部分文字列のセットを見つけることができます。

• Nの長さの文字列を入力します。

• 整数関数countSubstring（int N、string s）は、文字列と文字列の長さを入力として受け取り、「1」で始まり「1」で終わるすべての部分文字列の数を返します。

• 文字列全体を繰り返し、番号を数えます。文字列の「1」の。

• いいえを数えます。与えられた文字列の部分文字列（ペア）のn *（n-1）/2による。

• n *（n-1）/2の結果を返します。

例

#include<iostream>
using namespace std;
int countSubstring(int N, string s){
   int count=0;
   for(int i=0; s[i]!= '\0'; ++i){
      if( s[i]== '1' )
         count++;
   }
   return count*(count-1)/2;
}
int main() {
   int N=5;
   string str= "11101";
   cout<< countSubstring(N,str)<<endl;
   return 0;
}

出力

上記のコードを実行すると、出力は次のように出力されます。

6

指定された文字列に存在する「1」の数は「4」、つまりカウント=4であるため、「1」で始まり「1」で終わる部分文字列の総数は4 *（4-1）/2になります。 =6.