目次

• 問題
  • 入力
  • 出力
• 解説
• 計算量
• 解答

# 問題

https://atcoder.jp/contests/kupc2015/tasks/kupc2015_a

# 入力

T
S1
S2
...
St

• T - 文字列の数
• Si - tokyoまたはkyotoを１つ以上含む可能性のある文字列.

# 出力

N1
N2
...
Nt

それぞれの文字列からtokyoまたはkyotoを何個切り出すことが出来るかを答える問題です.

# 解説

文字列の先頭から検索し、tokyoまたはkyotoが見つかる度にそこまでの部分をすべて切り捨てて行けばOKです.
とにかく最初から見つかったほうを優先して切り取っていけば、残る文字列にtokyoかkyotoが見つかる可能性が高まるからです.
見つからなくなるか、文字列が空になったら終了です.
これをすべての文字列について繰り返します.

# 計算量

文字列の最大数を$T$、検索対象文字列の最大長を$N$、検索される文字列の最大長を$M$とします.
検索される文字列から対象文字列を切り出せる数の最大値は$\frac{M}{N}$です.
１回切り出すごとにfindを実行しこれはC++の仕様では計算量未定義ですが、gccの実装では$O(MN)$です.

$N$同士はキャンセルされます.

$O(TM^2)$

今回は$T$も$M$もともに$10^2$です.
十分に間に合います.

${10^2}^3 = 10^6$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

Int N;
vector<string> S;

void input() {
  cin >> N;
  string s_;
  while (cin >> s_) {
    S.push_back(s_);
  }
}

void solve() {
  for (auto s: S) {
    Int count = 0;
    loop(i,0,s.length()) {
      Int m1 = (int)s.find("tokyo", i);
      Int m2 = (int)s.find("kyoto", i);
      if (m1 == -1 && m2 == -1) break;
      if (m1 == -1) i = m2;
      else if (m2 == -1) i = m1;
      else i = min(m1, m2);
      i += 4;
      count++;
    }
    cout << count << endl;
  }
}

int main() {
  input();
  solve();
  return 0;
}