ある文字列中の指定文字列の個数を数える関数を自作する【競技プログラミング】

はじめに

• 競技プログラミングをしていれば、ある文字列の中に、指定文字列がいくつあるか数え上げるケースがある気がする。
• そんなの、どの言語でも当然関数が用意されているだろ！と思ったけど、「指定文字列が含まれるか？」という関数は存在しても、「指定文字列がいくつあるか？」という関数は、swiftで見つからなかったよ。

c++の場合

• swiftにないのはいつものことだから、"やれやれ、またかよ、c++には当然あるんだろうな〜"と思ったけど、c++にも存在しない模様。
• 存在するのは、strstr（第1引数、第2引数）関数で、文字列中の「ある文字列（第1引数）において、指定文字列（第2引数）が最初に現れる位置はどこか？」という関数だった。

#include <string.h>
char * strstr(const char *str1, const char *str2);

• 個数を数えたければ、この関数を使って、以下のようなプログラムを書くしかなかった。
• swiftもc++の系列といえるから、なんとなく、以下のプログラムで何をやってるか分かるでしょ？

#include <bits/stdc++.h>
using namespace std; 

int main(void) {
  const char* text = "aabcc,abcbabccab,cabc,aaabcccc";//文字列
  const char* word = "abc";//検索対象
  auto len = strlen(word);//検索対象の指定文字数
  
  auto cnt = 0; //一致数を数え上げる
  const char* ptr = text; //ポインタの初期位置
  while (1) {
    ptr = strstr(ptr, word); //発見した検索対象のポインタ位置を返す
    if (ptr != NULL) {
      cnt++;
      ptr += len; //ポインタの位置を文字数分動かす
    }
    else {
      break;
    }
  }
  
  cout << "cnt:" << cnt << endl; // cnt:5
}

• swiftでもstrstrのような関数があれば同じことが出来る。さて、似た関数はあるだろうか？

swiftの場合

• 少し嫌だけど、NSRangeとかのNS系の古くさい技術を使えば、c++のstrstr関数と似たことが出来る。
• 具体的には、range関数。ただし、使うときは、import Foundationが必要。

func range(of: String) -> NSRange
// Finds and returns the range of the first occurrence of a given string within the string.
func range(of: String, options: NSString.CompareOptions, range: NSRange) -> NSRange
// Finds and returns the range of the first occurrence of a given string, within the given range of the string, subject to given options.

// 実例
import Foundation
let str = "abcdefg"
let rng0 = str.startIndex..<str.endIndex
print(rng0) // Index(_rawBits: 1)..<Index(_rawBits: 458753)
let rng1 = str.range(of: "de")
print(rng1) // Optional(Range(Swift.String.Index(_rawBits: 196608)..<Swift.String.Index(_rawBits: 327680)))
let rng2 = str.range(of:"hi")
print(rng2) // nil

• 上記を使うと、文字列中の指定文字列の「範囲」がわかる。指定文字列の先頭位置ではないけど、範囲には先頭位置とお尻の位置が含まれるから、strstrの位置情報より情報量が多いので代用できる。大は小を兼ねるという奴だね。というか、strstrを使ったときには、strlenで検索文字の長さを取得する必要があったけど、rangeの場合はお尻の位置情報が含まれるから、strlenのような別関数による処理がいらないね。すごいぞNS系！
• さて、コレを使って、文字列中の検索文字列の数を数えるコードは以下の通り

import Foundation

let text = "aabcc,abcbabccab,cabc,aaabcccc"
let word = "abc"

var cnt = 0
var searchRng = text.startIndex..<text.endIndex
while true {
    guard let rng = text.range(of:word,range:searchRng) else {break}
    cnt += 1
    searchRng = rng.upperBound..<text.endIndex //upperBoundは、指定文字列のお尻の後ろのindex
}

print("cnt:",cnt) //  cnt: 5

• それにしても、いつも思うけど、while trueって、なんか嫌だよね。trueを省略させてくれと思う。true不要のloopみたいなコマンド作ってくれないかな。もしくは、repeat-while構文でwhile文を省略可能にするとかさ。
• 話が逸れたけど、range関数を使って、欲しい機能を関数化すると、こんな感じかな？

import Foundation
func cntStr(_ text:String,_ word:String)->Int{
    var cnt = 0
    var searchRng = text.startIndex..<text.endIndex
    while true {
        guard let rng = text.range(of:word,range:searchRng) else {break}
        cnt += 1
        searchRng = rng.upperBound..<text.endIndex
    }
    return cnt
}

let text = "abcabcabcabcabcabcabcabc"
let word = "abc"
print(cntStr(text,word)) // 8
print(cntStr(text,"d")) // 0

• これだけだと、少しつまらないから、text="ababababa",word="aba"のときに、カウントを4にするようなモードも追加してみる。前記のコードでは、最初のabaを検索した後、そのabaの直後のbから検索を再開するから、カウントが合計で2になるけど、追加するモードでは、最初のabaを検索した後、そのabaの2文字目から検索を再開するので、abaの3文字目からのabaが2カウント目になり、合計して4カウントとなる。

import Foundation

func cntStr(_ text:String,_ word:String,_ cntmode:Bool = true)->Int{
    var cnt = 0
    var searchRng = text.startIndex..<text.endIndex
    while true {
        guard let rng = text.range(of:word,range:searchRng) else {break}
        cnt += 1
        if cntmode {
            searchRng = rng.upperBound..<text.endIndex
        } else {
            searchRng = text.index(rng.lowerBound,offsetBy:1)..<text.endIndex //lowerBoundは指定文字列の先頭位置のindex
        }
    }
    return cnt
}

let text="ababababa"
let word="aba"

print(cntStr(text,word)) // 2
print(cntStr(text,word,false)) // 4

• 作ってはみたものの、strstrを使ったときのような速度が出るかは不明。特に、最後に作ったコードのポインタ処理もどきは、range関数の他、text.index(rng.lowerBound,offsetBy:1)があって、処理が重そうな気もする。strstrを使った場合のポインタ処理なんて、ptr = strstr(ptr, word)とptr += lenだけで、後者は当然爆速だし、strstrも速いんだろうなぁ。
• とりあえず、AtCoderでstrstrを使うような問題を見つけて、swiftで解けるか試してみる。

競技プログラミングの問題で実践

• ごめんなさい、20分ほど検索したけど見つかりませんでした。そのうち見つけたら、追記します。

おわりに

• 文字列text中に指定文字列wordがいくつあるか？というメソッドなんて、標準で存在すると思っていたけど、なんでないんだろ？
• まぁ、文字列っていうのは、実際はユニコードだったり、二バイト文字だったり色々種類もあるから、標準的に作っても駄目なのかもね。
• とりあえず、AtCoderで必要となる機会もあるだろうから、まぁ、作って良かったと思うことにする。