[C++]白駿8933号:MCS

13878 ワード
白駿 ツリーのコレクションとマッピングの使用 スライドウィンドウ データ構造 ハッシュのセットとマッピングの使用 テキストリンク
質問リンク
8933号：MCS
問題の概要
{A,G,T,C}の個数が同じ文字列が同じ文字列に合成される.文字列が与えられた場合、その文字列にはkの長さの部分文字列が存在する.この部分の文字列の中で、同じ文字列を合成するのが最も多いものをk-MSSと呼ぶ.この場合はk-MCSの出場回数を求める必要がある.
方法
これはマッピングを使用する基本的な問題です.
  • ウィンドウを移動し、ウィンドウ内のA、G、T、およびCの数を計算します.
    • A、G、T、Cの数をキーとして、マッピングでは1回あたり
  • が検索される.存在しない場合はvalueを1に追加し、存在する場合は1を追加します.
  • ウィンドウを最後に移動すると、マッピングの開始位置で最大値が検索されます.
    • これは簡単な問題ですが、私の場合、ツリー図を使用し、構造体をキーとして使用し、コードが少し長いようです.
    コード#コード#
    #include <bits/stdc++.h>

using namespace std;

struct Info {
	int a, g, c, t;

	bool operator<(const Info& info) const
	{
		if (a == info.a)
		{
			if(g == info.g)
			{
				if (c == info.c)
					return t < info.t;
				return c < info.c;
			}
			return g < info.g;
		}
		return a < info.a;
	}
};

map<Info, int> m;

int func(char c)
{
	switch (c)
	{
	case 'A':
		return 0;
	case 'G':
		return 1;
	case 'C':
		return 2;
	case 'T':
		return 3;
	}
}

void add(vector<int>& v)
{
	if (m.find({ v[0], v[1], v[2], v[3] }) == m.end())
		m.insert({ { v[0], v[1], v[2], v[3] }, 1 });
	else
		m[{v[0], v[1], v[2], v[3]}]++;
}

int main(void)
{
	int t;
	cin >> t;

	while (t--)
	{
		int k;
		string str;
		cin >> k >> str;

		vector<int> v(4, 0);
		for (int i = 0; i < k; i++)
			v[func(str[i])]++;

		add(v);
		for (int i = k; i < str.size(); i++)
		{
			v[func(str[i])]++;
			v[func(str[i - k])]--;
			add(v);
		}

		int res = 0;
		for (map<Info, int>::iterator it = m.begin(); it != m.end(); it++)
			res = max(res, it->second);
		cout << res << '\n';
		m.clear();
	}

	return 0;
}
    [混攻学習団第7期]混攻派第1週
    Androidでブラウザを呼び出してWebページを開く方法