Submission #1133539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133539		79brue	Joyful KMP (KRIII5_JK)	C++20	0 / 1	12 ms	24132 KiB

JK

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

int n;
string str;

int fail[1010101];

int cnt;
int grp[1010101];

vector<int> adj[1010101];

void kmp() {
	int i = 1;
	int j = 0;

	cnt = 1;

	vector<int> v;

	while (i < n) {
		if (str[i] == str[j]) {
			grp[i] = grp[j];

			for (int dif : v) {
				adj[grp[i]].push_back(dif);
			}

			v.clear();

			fail[i] = j + 1;
			i++, j++;
		}
		else {
			v.push_back(grp[j]);

			if (j == 0) {
				grp[i] = cnt++;

				for (int dif : v) {
					adj[grp[i]].push_back(dif);
					adj[dif].push_back(grp[i]);
				}

				v.clear();

				i++;
			}
			else {
				j = fail[j - 1];
			}
		}
	}
}

int now = 0;

bool deleted[1010101];
int delcnt = 0;

ll solve() {
	for (int i = now; i < cnt; i++) {
		if (adj[i].empty() || deleted[i]) continue;

		now = i;

		ll ans = 0;

		int j = adj[i].back();

		adj[i].pop_back();
		if (adj[j].back() != i) remove(adj[j].begin(), adj[j].end(), i);
		else adj[j].pop_back();

		ans += solve();

		for (int k : adj[j]) {
			if (find(adj[i].begin(), adj[i].end(), k) == adj[i].end()) adj[i].push_back(k);
			if (find(adj[k].begin(), adj[k].end(), i) == adj[k].end()) adj[k].push_back(i);

			remove(adj[k].begin(), adj[k].end(), j);
		}

		adj[j].clear();

		deleted[j] = true;
		delcnt++;

		ans -= solve();

		return ans;
	}

	ll ans = 1;

	for (int i = 0; i < cnt - delcnt; i++) {
		ans *= 26;
		ans %= 1000000007;
	}

	return ans;
}

ll order = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> str;
	n = (int)str.size();

	cin >> order;

	kmp();

	for (int i = 0; i < cnt; i++) {
		sort(adj[i].begin(), adj[i].end());
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
	}

	cout << solve() << "\n";

	return 0;
}

• Subtask 1: 0 / 1