rockdu
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.
The first line contains a single integer nn (1≤n≤401≤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'.
Print the only integer — the number of distinct cyclical binary strings tt, which contain ss as a substring.
20
3
4 1010
2
20 10101010101010
962
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;
}
没有帐号? 立即注册