[접미사 로봇 DP] LOJ#6071.'2017 산동 1차 훈련Day5'문자열
그러면 DP의 이동은 접미사 자동기로 할 수 있어요.
#include
#include
#include
#include
using namespace std;
const int N=4000010,P=1e9+7;
int n,cnt=1,len;
int nxt[N][30],fail[N],f[30],stp[N],t[N],r[N],g[N],p=1;
char a[N];
inline void extend(int x){
int np=++cnt; stp[np]=stp[p]+1;
while(p && !nxt[p][x]) nxt[p][x]=np,p=fail[p];
if(!p) fail[np]=1;
else{
int q=nxt[p][x];
if(stp[q]==stp[p]+1) fail[np]=q;
else{
int nq=++cnt; stp[nq]=stp[p]+1;
memcpy(nxt[nq],nxt[q],sizeof(nxt[nq]));
fail[nq]=fail[q];
fail[q]=fail[np]=nq;
while(p && nxt[p][x]==q) nxt[p][x]=nq,p=fail[p];
}
}
p=np;
}
int main(){
scanf("%d",&n);
while(n--){
scanf("%s",a+1); len=strlen(a+1);
for(int i=len;i;i--) extend(a[i]-'a');
for(int i=0;i<=cnt;i++) t[i]=0;
for(int i=1;i<=cnt;i++) t[stp[i]]++;
for(int i=1;i<=cnt;i++) t[i]+=t[i-1];
for(int i=1;i<=cnt;i++) r[t[stp[i]]--]=i;
for(int i=cnt;i;i--){
int x=r[i]; g[x]=1;
for(int j=0;j<26;j++)
if(nxt[x][j]) (g[x]+=g[nxt[x][j]])%=P;
else (g[x]+=f[j])%=P;
}
for(int i=0;i<26;i++)
if(nxt[1][i]) f[i]=g[nxt[1][i]];
for(int i=1;i<=cnt;i++){
stp[i]=fail[i]=0;
for(int j=0;j<26;j++) nxt[i][j]=0;
}
cnt=p=1;
}
int ans=0;
for(int i=0;i<26;i++) (ans+=f[i])%=P;
printf("%d
",ans+1);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.