Boj 25564) 역삼역

문제

백준 25564

설명

서로다른 부분 문자열은 LCP Array 로 구할 수 있다. 요약하면 모든 부분 문자열은 Suffix 의 Prefix 라고 생각할 수 있고, 그 중 중복인 것은 LCP Array 의 값과 같다.

팰린드롬은 매내처 알고리즘을 사용하면 문자열의 인덱스마다 그것을 중심으로 한 팰린드롬의 반지름을 얻을 수 있다. 팰린드롬은 앞뒤를 떼어내도 팰린드롬이므로, 인덱스마다 K 보다 크면서 가장 작은 길이의 부분 팰린드롬을 얻을 수 있다. 이를 G 라고 하자.

Suffix 의 시작 인덱스 i 가 주어졌을 때

• 중복되지 않는 모든 부분문자열은 i + lcp[rk[i]] 부터 시작하는 Prefix 가 된다.
• 팰린드롬을 포함하는 부분문자열은 G 중에서 끝이 i 보다 크면서 가장 작은 부분 팰린드롬을 포함해야한다.

두 조건을 합치면 아래와 같은 코드를 얻을 수 있다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}\))

코드

const int MAXIN = 506000;

template<int SIZE = MAXIN, int CSIZE = 27>
struct SuffixArray
{
	string src; int len = -1;
	int sa[SIZE], lcp[SIZE];

	// 내부사용값
	int rk[SIZE], cnt[SIZE], tmp[SIZE];
	int o = 1;

	inline bool Cmp(int a, int b)
	{
		if (rk[a] != rk[b]) return rk[a] < rk[b];
		if (a + o < len && b + o < len)
			return rk[a + o] < rk[b + o];
		return  a + o > b + o;
	}

	void CountSort()
	{
		int m = max(rk[sa[len - 1]] + 1, CSIZE) + 1;
		fill(cnt, cnt + m, 0);
		for (int i = 0; i < len; i++) cnt[i + o < len ? rk[i + o] + 1 : 0]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (int i = len - 1; i >= 0; i--) tmp[--cnt[i + o < len ? rk[i + o] + 1 : 0]] = i;

		fill(cnt, cnt + m, 0);
		for (int i = 0; i < len; i++) cnt[rk[i]]++;
		for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
		for (int i = len - 1; i >= 0; i--) sa[--cnt[rk[tmp[i]]]] = tmp[i];
	}

	void Init()
	{
		len = src.size();
		int p, i;

		//Manber-Myers Algorithms
		for (i = 0; i < len; i++) rk[i] = src[i] - 'a';
		for (p = 0, o = 1; p + 1 < len; o <<= 1)
		{
			CountSort();
			p = tmp[sa[0]] = 0;
			for (int i = 1; i < len; i++)
				tmp[sa[i]] = Cmp(sa[i - 1], sa[i]) ? ++p : p;
			swap(tmp, rk);
		}

		// Kasai Algorithms
		// 여기서는 len 이 1 인경우 rank 가 알파벳 오프셋이 되어 작동하지 않음에 주의
		int num = 0;
		for (int i = 0; i < len; i++)
		{
			int k = rk[i];
			if (k) {
				while (src[i + num] == src[sa[k - 1] + num]) num++;
				lcp[k] = num;
				if (num) num--;
			}
		}
	}
};
SuffixArray sf;

char in[MAXIN * 2]; int n, k;
int dp[MAXIN * 2];
void Manacher()
{
	int r = 0, p = 0;
	for (int i = 0; i < n; i++)
	{
		if (i <= r)
			dp[i] = min(dp[p * 2 - i], r - i);
		else
			dp[i] = 0;

		// i 를 중심으로 가능한 팰린드롬의 반지름을 하나씩 비교하며 계산
		while (i - dp[i] - 1 >= 0 && i + dp[i] + 1 < n && in[i - dp[i] - 1] == in[i + dp[i] + 1])
			dp[i]++;

		// 기준 팰린드롬 업데이트
		if (r < i + dp[i])
		{
			r = i + dp[i];
			p = i;
		}
	}
}

char s[MAXIN];

long long Solve()
{
	// 짝수로 확장한 Manacher
	for (int i = n - 1; i >= 0; i--) in[(i << 1) + 1] = s[i];
	for (int i = 0; i <= n; i++) in[i << 1] = '#';
	n = n * 2 + 1;
	Manacher();

	vector<pair<int, int>> goods; // start, count
	for (int i = 0; i < n; i++)
		if (dp[i] >= k)
		{
			if ((dp[i] & 1) == (k & 1))
				goods.push_back({ i / 2 - k / 2, k });
			else
				goods.push_back({ i / 2 - (k + 1) / 2, k + 1 });
		}
		

	sf.src = s;
	sf.Init();

	long long ans = 0;
	for (int i = 0, j = 0; i < sf.len; i++)
	{
		while (j < goods.size() && i > goods[j].first) j++;
		if (j == goods.size()) break;
		
		// substr => prefix start from sf.sa[i] + sf.lcp[i], 
		int idx = max(goods[j].first + goods[j].second - 1, i + sf.lcp[sf.rk[i]]);
		ans += sf.len - idx;
	}

	return ans;
}

int main()
{
	scanf("%d %d", &n, &k);
	scanf("%s", s);

	cout << Solve();
}