Rikka with String

http://acm.hdu.edu.cn/showproblem.php?pid=6086

题意:

  求一个长度为2L的,包含所给定的n的串,并且满足非对称。

分析:

  AC自动机+状压dp。

  首先给这个n个串,建立AC自动机。然后去枚举长度为L的一个串,就可以知道另一半了。

  如果给定的串完全存在于左边或者右边,那么直接往AC自动机加入这个串或者取反后的反串。如果是跨越中间,那么暴力的把所有的串,从中间切开,然后判断是否合法,加入到AC自动机上就行,如果长度枚举到了i-1的时候,这些串的状态才有用。

代码:

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int mod = ;
int ch[][], sta1[], sta2[], fail[], q[], dp[][][];
int Index;
char s[], t[], a[], b[]; void Insert(char *s,int n,int id,bool f) {
int u = ;
for (int i = ; i < n; ++i) {
int c = s[i] - '';
if (!ch[u][c]) ch[u][c] = ++Index;
u = ch[u][c];
}
if (f) sta1[u] |= ( << id);
else sta2[u] |= ( << id);
}
void build() {
int L = , R = ;
for (int i = ; i < ; ++i) if (ch[][i]) q[++R] = ch[][i];
while (L <= R) {
int u = q[L ++];
for (int c = ; c < ; ++c) {
int v = ch[u][c];
if (!v) { ch[u][c] = ch[fail[u]][c]; continue; }
int p = fail[u]; while (p && !ch[p][c]) p = fail[p];
q[++R] = v;
fail[v] = ch[p][c];
sta1[v] |= sta1[fail[v]], sta2[v] |= sta2[fail[v]];
}
}
}
void update(char *s,int n,int id) {
int c1 = , c2 = , f = ;
for (int i = ; i < n - ; ++i) {
c1 = c2 = f = ;
for (int j = i; j >= ; --j) a[c1 ++] = s[j];a[c1] = '\0';
for (int j = i + ; j < n; ++j) b[c2 ++] = s[j]; b[c2] = '\0';
for (int j = ; j < c1 && j < c2; ++j) if (a[j] == b[j]) { f = ; break; }
if (f) continue;
for (int j = c1; j < c2; ++j) a[j] = b[j] == '' ? '' : '';
reverse(a, a + max(c1, c2));
Insert(a, max(c1, c2), id, ); // 长度为max(c1,c2)!!!
}
}
void init() {
memset(dp, , sizeof(dp));
memset(ch, , sizeof(ch));
memset(fail, , sizeof(fail));
memset(sta1, , sizeof(sta1));
memset(sta2, , sizeof(sta2));
}
inline void add(int &x,int y) { x += y; if (x >= mod) x -= mod; }
void solve() {
init();
int n = read(), L = read(), len;
for (int i = ; i < n; ++i) {
scanf("%s", s); len = strlen(s);
Insert(s, len, i, );
for (int j = ; j < len; ++j) t[j] = s[j];
reverse(t, t + len);
for (int j = ; j < len; ++j) t[j] = t[j] == '' ? '' : '';
Insert(t, len, i, );
update(s, len, i);
}
build();
dp[][][] = ;
int All = ( << n) - , now = ;
for (int i = ; i < L; ++i, now ^= )
for (int j = ; j <= Index; ++j)
for (int s = ; s <= All; ++s) {
if (dp[now][j][s] <= ) continue;
for (int c = ; c < ; ++c) {
int nv = ch[j][c], ns = s | sta1[nv];
if (i == L - ) ns |= sta2[nv];
add(dp[now ^ ][nv][ns], dp[now][j][s]);
}
dp[now][j][s] = ;
}
int ans = ;
for (int i = ; i <= Index; ++i) add(ans, dp[now][i][All]);
printf("%d\n",ans % mod);
}
int main() {
for (int T = read(); T --; ) solve();
return ;
}

最新文章

  1. 重学hadoop技术
  2. Java反射机制调用private类型的构造方法
  3. 在Android Studio中用Gradle添加Robolectric
  4. ubuntu用户添加adduser, useradd
  5. 兼容IE的CSS的”引入方式“
  6. Hibernate反转维护
  7. HDU 4822 Tri-war(LCA树上倍增)(2013 Asia Regional Changchun)
  8. python logger
  9. django 创建数据库表的linux命令
  10. 为网页设计师准备的30个使用的HTML5框架
  11. rabbitMQ安装及部署
  12. SQL 多条件查询
  13. MySQL注入总结
  14. call, apply &amp;&amp; bind, currying
  15. Django|第一部
  16. Jmeter连接mysql数据库
  17. 获得当前EIP的值
  18. mysql 水平分表
  19. MATLAB简易画图2—普通直角坐标系
  20. makefile 常用函数

热门文章

  1. tcp的三次握手:通信的本质:通信通知与信息交换
  2. BZOJ1972:[SDOI2010]猪国杀(模拟)
  3. python3通过qq邮箱发送邮件
  4. rand7生成rand10,rand1生成rand6,rand2生成rand5(包含了rand2生成rand3)
  5. 数据包式套接字:基于UDP协议的Socket网络编程
  6. 崩溃!UIAlertController 引起的崩溃
  7. RSA加密算法和签名算法
  8. LeetCode39.组合总和 JavaScript
  9. Objective-C 之深拷贝和浅拷贝
  10. element UI 饿了么 UI 分页 按钮不显示的问题