ACM-ICPC 2016 Asia Tsukuba Regional, D 解法

D: Hidden Anagrams

問題

2つの同じ長さの文字列が、各アルファベットの出現数が同じであるとき、互いにアナグラムであると言う（多分同じ文字列もアナグラムという）。
2つの文字列が与えられる。それぞれから部分文字列を取り出して、それらがアナグラムであるようなとき、その部分文字列の長さの最大値を求めよ。
アルファベットはa~z、文字列の長さはそれぞれ4000以下。10sec。

解法

片方の文字列のすべての部分文字列をアルファベットの出現数の配列にして、辞書順ソート。もう一つの文字列の部分文字列も同様に出現数を出して、二分探索で検索する。
TLEが長いので何をやっても大丈夫かと思ったがメモリのほうが厳しかった。文字列の長さごとに開放すればよい。

コード

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<assert.h>
using namespace std;

typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

char S[4111], T[4111];
int N, M;
vector<vector<int> > arr;
int C[26];

int main() {

    scanf("%s", S);
    N = strlen(S);

    scanf("%s", T);
    M = strlen(T);

    int ans = 0;

    for (int len=1; len<=min(N, M); len++) {
	arr.clear();
	memset(C, 0, sizeof C);
	REP (i, len) C[S[i]-'a']++;
	for (int i=len; i<=N; i++) {
	    arr.push_back(VI(C, C+26));

	    if (i < N) {
		C[S[i]-'a']++;
		C[S[i-len]-'a']--;
	    }
	}

	sort(arr.begin(), arr.end());

	memset(C, 0, sizeof C);
	REP (i, len) C[T[i]-'a']++;
	for (int i=len; i<=M; i++) {
	    VI key(C, C+26);
	    int k = lower_bound(arr.begin(), arr.end(), key) - arr.begin();
	    if (k < (int)arr.size() && arr[k] == key) {
		ans = len;
		break;
	    }

	    if (i < M) {
		C[T[i]-'a']++;
		C[T[i-len]-'a']--;
	    }
	}
    }

    printf("%d\n", ans);

    return 0;
}

感想

始めTrieかと思った。