C++で指定したパターンで終わる文字列の個数を数える方法

問題概要

文字列の配列 str[] と、パターン文字列 pat が与えられます。この記事の目的は、str[] の要素の中から、末尾がパターン pat と一致する文字列を見つけ出し、その個数を数えることです。

解決のアプローチはシンプルです。配列内の各文字列を順番に走査し、末尾の文字を pat と比較します。一致した場合はカウントを1つ増やします。

具体例を使って確認してみましょう。

入力

str[]={ "kittens", "hens", "deers", "dogs" } pat="ens"

出力

指定されたパターンで終わる文字列: 2

説明

"kittens" と "hens" の2つの文字列が "ens" で終わっています。

入力

str[]={ "tickets", "wickets", "bats", "cricket" } pat="et"

出力

指定されたパターンで終わる文字列: 1

説明

"wickets" のみが "et" で終わっています。

使用するアルゴリズムの手順

• 文字列配列 str[] とパターン文字列 pat を受け取ります。

• N は str[] に含まれる文字列の総数です。

• 関数 endPattern(string str[], int n, string ptr) は、与えられたパターンで終わる str 内の文字列の個数を返します。

• 初期値として変数 count を 0 に設定します。

• i=0 から i<n まで for ループで各文字列を走査します。

• 各文字列 str[i] を s とし、slen を s.length() とします。

• plen=ptr.length() とし、flag=1 に設定します。

• slen と plen から 1 を引くことで、文字列 s とパターン ptr のそれぞれの末尾のインデックスを取得します。

• while ループを使い、plen>=0 である限り処理を繰り返します。

• s[slen]!=ptr[plen] となった場合は flag=0 に設定してループを抜けます。そうでなければ plen と slen を減らし、末尾から次の文字をチェックしていきます。

• while ループ終了後も flag が 1 のままであれば、パターン ptr が文字列 s の末尾に存在するため、count をインクリメントします。

• すべてのループが完了した後に count を返します。これが指定されたパターンで終わる文字列の個数です。

コード例

#include <bits/stdc++.h>
using namespace std;
int endPattern(string str[], int n, string ptr){
    int count=0;
    for(int i=0;i<n;i++){
        string s=str[i];
        int slen=s.length();
        int plen=ptr.length();
        int flag=1;
        slen--; //末尾のインデックス
        plen--;
        while(plen>=0){
            if(ptr[plen]!=s[slen]){
                flag=0;
                break;
            }
            plen--;
            slen--;
        }
        if(flag==1)
            { count++; }
    }
    return count;
}
int main(){
    string patrn = "pes";
    int N = 4;
    string str[] = { "stripes", "cars", "ripes", "pipes" };
    cout <<"Strings that end with given pattern: "<<endPattern(str,N,patrn);
    return 0;
}

出力

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

Strings that end with given pattern: 3

まとめ

このアルゴリズムは、各文字列の末尾からパターンとの文字比較を行うことで、指定されたパターンで終わる文字列を効率的に判定できます。計算量は O(n×m)（n は文字列の本数、m はパターンの長さ）となり、簡潔かつ実用的な方法です。