CF#508 Div2 F. Wrap Around
? 解题记录 ? ? Codeforces ? ? KMP ? ? 动态规划 ?    2018-09-18 09:18:41    486    0    0

You are given a binary string ss.

Find the number of distinct cyclical binary strings of length nn which contain ss as a substring.

The cyclical string tt contains ss as a substring if there is some cyclical shift of string tt, such that ss is a substring of this cyclical shift of tt.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.

Input

The first line contains a single integer nn (1n401≤n≤40) — the length of the target string tt.

The next line contains the string ss (1|s|n1≤|s|≤n) — the string which must be a substring of cyclical string tt. String ss contains only characters '0' and '1'.

Output

Print the only integer — the number of distinct cyclical binary strings tt, which contain ss as a substring.

Examples
input
Copy
20
output
Copy
3
input
Copy
4
1010
output
Copy
2
input
Copy
20
10101010101010
output
Copy
962
Note

In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".

题意:给你一个01字符串t,问长度为n的01字符串s有多少个在循环意义下包含t。

这道题思路比较巧妙,有O(n^2)的做法但是我没看懂。

如果不考虑循环同构,那么这是个kmp上dp的裸题。

有了循环同构怎么办呢?考虑自动机匹配的本质,一个串在自动机上跑的路径经过一次匹配节点就被匹配一次,我们从这个匹配路径来考虑这道题。

一个循环串只要存在从一个位置开始跑kmp能经过匹配节点就包含了t串,我们枚举自动机上的每一个节点u开始往后做匹配,那么整条路径被分为了经过u前的和经过u后的,对于每一个u,我们只要dp出所有跑完自动机后以u结尾的串有多少个就枚举出了t串在s开头结尾分离的情况。换言之,我们从t串被分隔的情况考虑了所有的情况。

时间复杂度:O(n^3)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL dp[55][55][2], ans;
int n, m, fail[55], trans[55][2], v;
char s[55];

int GetF(int x, char c) {
	while(~x && s[x + 1] != c) x = fail[x];
	return ~x ? (x + 1) : 0;
}

void build() {
	int p;
	fail[0] = -1;
	for(register int i = 1; i <= m; ++i) {
		p = fail[i - 1];
		while(~p && s[p + 1] != s[i]) p = fail[p];
		if(~p) fail[i] = p + 1; else fail[i] = 0;
	}
	for(register int i = 0; i <= m; ++i) {
		trans[i][0] = GetF(i, '0');
		trans[i][1] = GetF(i, '1');
	}
}

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	m = strlen(s + 1);
	build();
	for(register int st = 0; st <= m; ++st) {
		memset(dp, 0, sizeof(dp));
		dp[0][st][0] = 1;
		for(register int i = 0; i < n; ++i) {
			for(register int j = 0; j <= m; ++j) {
				v = trans[j][0];
				dp[i + 1][v][v == m] += dp[i][j][0];
				dp[i + 1][v][1] += dp[i][j][1];
				v = trans[j][1];
				dp[i + 1][v][v == m] += dp[i][j][0];
				dp[i + 1][v][1] += dp[i][j][1];
			}
		}
		ans += dp[n][st][1];
	}
	printf("%I64d", ans);
	return 0;
}


上一篇: CF#509 Div2 E. Tree Reconstruction

下一篇: CF#507 Div1 D. You Are Given a Tree

486 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航