字符串训练之一
字符串训练
例题一
https://www.luogu.org/problem/P2292
给出 N个单词，和 M 个句子，问每个句子中包含这些单词的最长前缀是多少。
解题技巧:
提取关键字:句子......前缀.....
好的学过AC自动机的就应该知道了
但现在有要求是最长
又是个最值问题:dp?贪心?
在ac自动机中唯一能插入其他操作的只有查询fail数组的时候才行
此时问题已经解决了一大半了
核心来了
for(int y=x;y;y=fail[y])
if(is_end[y]&&exi[p+1-dep[y]]){
exi[p+1]=1;
break;
}仔细思考一下发现好像有那么的道理
为什么要break掉
因为再在fail中找只会越来越劣
如果这点没理解到就回去再学学自动机吧
code:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=20+5;
const int L=10+5;
const int M=0x100010;
template<class T>inline void read(T &num){
char ch;
while(!isdigit(ch=getchar()));
num=ch-'0';
while(isdigit(ch=getchar()))num=num*10+ch-'0';
}
int tri[N*L][26],dep[N*L],fail[N*L],is_end[N*L],totn,n,m;
int exi[M];
char str[M];
inline void Insert(char s[]){
int x=0,len=strlen(s);
for(int p=0;p<len;++p){
int ch=s[p]-'a';
if(tri[x][ch]==0){
tri[x][ch]=++totn;
dep[totn]=dep[x]+1;
}
x=tri[x][ch];
}
is_end[x]=1;
}
queue<int> que;
void Fail(){
int x=0;
for(int i=0;i<26;++i)if(tri[x][i])que.push(tri[x][i]);
while(que.size()){
x=que.front();que.pop();
for(int i=0;i<26;++i){
if(tri[x][i])fail[tri[x][i]]=tri[fail[x]][i],que.push(tri[x][i]);
else tri[x][i]=tri[fail[x]][i];
}
}
}
int AC(char str[]){
memset(exi,0,sizeof(exi));
exi[0]=1;
int x=0,len=strlen(str);
for(int p=0;p<len;++p){
int ch=str[p]-'a';
x=tri[x][ch];
for(int y=x;y;y=fail[y]){
if(is_end[y]&&exi[p+1-dep[y]]){
exi[p+1]=1;
break;
}
}
}
for(int i=len;i;--i)if(exi[i])return i;
return 0;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;++i){
scanf("%s",str);
Insert(str);
}
Fail();
for(int i=1;i<=m;++i){
scanf("%s",str);
printf("%d\n",AC(str));
}
return 0;
}1、linux系统——网络调试工具
2、安装mysql odbc遇到error 1918.errror installing ODBC driver mysql ODBC 5.3 ANSI Drive
3、sqoop提供数据库密码的4种方式
4、门面模式
5、用C＃动态创建Access数据库