【C++】最初と最後の文字が同じ部分文字列の数え方を解説

文字列 str が与えられたとき、その中に含まれる「最初と最後の文字が同じ」部分文字列の個数を数えるのが本記事の目的です。

例えば、入力が "baca" の場合、条件を満たす部分文字列は "b"、"a"、"c"、"a"、"aca" の5つになります。

それでは、具体的な例を使って理解していきましょう。

入力 − str="abaefgf"

出力 − 最初と最後の文字が同じ部分文字列の数:9

説明 − 条件を満たす部分文字列は以下の通りです。

"a", "b", "a", "e", "f", "g", "f", "aba", "fgf"。合計9個。

入力 − str="abcdef"

出力 − 最初と最後の文字が同じ部分文字列の数:6

説明 − 条件を満たす部分文字列は以下の通りです。

"a", "b", "c", "d", "e", "f"。合計6個。

プログラムで使用するアプローチ

この問題を解く方法は複数あります。ここでは「ナイーブ(素朴)なアプローチ」と「効率的なアプローチ」の2つを紹介します。まずはナイーブなアプローチから見ていきましょう。すべての長さの部分文字列を関数 check() に渡し、その部分文字列の先頭と末尾が同じ文字であればカウントを1つ増やします。

• 文字列 str を受け取り、長さを str.size() で計算します。

• 関数 check(string str) は部分文字列を受け取り、先頭と末尾の文字が一致するか(str[0]==str[length-1])を判定します。一致すれば1を返します。

• 関数 check_Start_End(string str, int length) は文字列とその長さを引数に取り、先頭と末尾の文字が同じ部分文字列の総数を返します。

• 初期カウントを0に設定します。

• 二重のforループで文字列を走査します。外側のループは i=0 から i<length まで、内側のループは j=1 から j<length-i まで繰り返します。

• substr(i,j) を使ってあらゆる長さの部分文字列を生成し、それぞれを check() に渡します。戻り値が1ならカウントを増やします。

• 両方のループが完了した時点で、カウントには条件を満たす部分文字列の総数が格納されています。

• カウントを結果として返します。

効率的なアプローチ

実は、この問題の答えは元の文字列における各文字の出現回数だけで決まります。

例えば "bacba" の場合、'b' の出現回数は2回で、'b' を端に持つ部分文字列は "b"、"bacb"、"b" の3つです。これは 2+₂C₂=3 と計算できます。

つまり、各文字について出現回数 freq を求め、freq×(freq+1)/2 を答えに加算していけばよいのです。計算量は O(n) となり、非常に高速です。

• 文字列 str を受け取り、長さを str.size() で計算します。

• 関数 check_Start_End(string str, int length) は文字列とその長さを引数に取り、先頭と末尾の文字が同じ部分文字列の総数を返します。

• 初期カウントを0に設定します。

• 各文字の出現回数を格納するための配列 arr[26] を用意します。

• 文字列を走査しながら、arr[str[i]-'a']++ として出現回数を記録します。

• 出現回数配列 arr[26] を走査し、各要素 arr[i] に対して arr[i]*(arr[i]+1)/2 をカウントに加算します。

• 最後にカウントを結果として返します。

サンプルコード(ナイーブなアプローチ)

#include <bits/stdc++.h>
using namespace std;
int check(string str){
    int length = str.length();
    if(str[0] == str[length-1]){
        return 1;
    }
}
int check_Start_End(string str, int length){
    int count = 0;
    for (int i = 0; i < length; i++){
        for (int j = 1; j <= length-i; j++){
            if (check(str.substr(i, j))){
                count++;
            }
        }
    }
    return count;
}
int main(){
    string str = "bcbdedfef";
    int length = str.length();
    cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

Count of substrings with same first and last characters are: 13

サンプルコード(効率的なアプローチ)

#include <bits/stdc++.h>
using namespace std;
#define maximum 26
int check_Start_End(string str, int length){
    int count = 0;
    int arr[maximum] = {0};
    for(int i=0; i<length; i++){
        arr[str[i] - 'a']++;
    }
    for (int i=0; i<maximum; i++){
        count = count + (arr[i]*(arr[i]+1)/2);
    }
    return count;
}
int main(){
    string str = "bcbdedfef";
    int length = str.length();
    cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

Count of substrings with same first and last characters are: 13