[AC 로봇+DP] 일치(match)
[제목 대의] k개의 문자열과 길이가 n인 모열의 선택할 수 있는 자모의 집합을 정하고 모열은 정해진 k개의 문자열을 완전하게 나타내는 방안수를 묻는다. 답안 모드는 1000000007이고 문자는 소문자만 포함한다.
(n<=100, m<=10, k<=8, 주어진 문자열 길이<=30)
[문제풀이] 원래 이 문제는 비교적 물이 많은 문제였는데, 방금 더 빠른 AC자동기를 만드는 방법을 배웠기 때문에 이 연습을 손에 넣었다.
주어진 k개의 문자열에 대해 AC 로봇을 설정합니다.f[i][j][k]를 설정하여 현재 i위(총 N위)를 달성하고 자동기기의 j노드는 k상태의 문자열(k는 2진법으로 표시)의 방안 수와 일치합니다.
f[i][j][k]는 f[i+1][j][k], (j=t[j].son[p], k=k or t[j].stat, p는 열거의 다음 문자)로 이동할 수 있습니다.
만약 j노드에 문자p라는 아들이 없다면 우리는 자동기의 성질에 따라 j노드의fail(교체)에서 문자p가 아들로 있는 노드를 찾고 그 노드로 뛰어야 한다(이렇게 하면 일치성을 확보할 수 있다).이 조작은 이런 새로운 ac자동기를 건설하는 방법에서 완벽하게 해결되었다.
기존 코드:
void Construct_fail()
{
static int d[maxm];
int l = 0, r = 1;
while (l < r)
{
int x = d[++l];
fo(i,0,25)
if (trie[x].son[i])
{
int v = trie[x].son[i];
if (x == 0) trie[v].fail = 0;
else
{
int p = trie[x].fail;
while (p && !trie[p].son[i]) p = trie[p].fail;
if (trie[p].son[i]) trie[v].fail = trie[p].son[i];
else trie[v].fail = 0;
}
d[++r] = v;
}
}
}
새로운 방법:
void Construct_fail()
{
static int d[3*maxn];
int l = 0, r = 1;
while (l < r)
{
int x = d[++l];
fo(p,1,M)
{
int i = a[p];
if (t[x].son[i])
{
int v = t[x].son[i];
if (x == 0) t[v].fail = 0;
else t[v].fail = t[t[x].fail].son[i];
t[v].stat |= t[t[v].fail].stat;
d[++r] = v;
} else t[x].son[i] = t[t[x].fail].son[i];
}
}
}
(p순환은 구체적인 제목의 요구)
새로운 구조 방법은while 순환을 절약하는 것을 발견할 수 있다. 만약에 노드 x에 i라는 아들이 없다면 우리는 직접 t[x]를 사용할 것이다.son[i] = t[t[x].fail].son[i];우리가 x 노드와 일치할 때, 다음 문자가 i라면, x의fail에서 i 아들이 있는 노드를 찾을 것입니다.따라서 직접 값을 부여하는 것이 정확하고 이 조작도 우리로 하여금 직접 t[v]를 할 수 있게 한다.fail = t[t[x].fail].son[i](약간의 복잡도를 최적화할 수 있다).
전체 코드:
#include
#include
#define fo(i,a,b) for (int i = a;i <= b;i ++)
using namespace std;
const int maxn = 105;
const int P = 1000000007;
int N,M,K,len,tot;
int f[maxn][3*maxn][1<<8];
int a[35],exist[35];
char s[35];
struct node
{
int son[26];
int fail,stat;
}t[3*maxn];
void Insert(int x,int i,int id)
{
int v = s[i] - 'a';
if (!t[x].son[v]) t[x].son[v] = ++tot;
if (i != len) Insert(t[x].son[v],i+1,id);
else t[t[x].son[v]].stat = 1 << (id-1);
}
void Make_trie()
{
scanf("%d%d",&N,&K);
fo(i,1,K)
{
scanf("%s",s+1);
len = strlen(s+1);
Insert(0,1,i);
}
}
void Construct_fail()
{
static int d[3*maxn];
int l = 0, r = 1;
while (l < r)
{
int x = d[++l];
fo(p,1,M)
{
int i = a[p];
if (t[x].son[i])
{
int v = t[x].son[i];
if (x == 0) t[v].fail = 0;
else t[v].fail = t[t[x].fail].son[i];
t[v].stat |= t[t[v].fail].stat;
d[++r] = v;
} else t[x].son[i] = t[t[x].fail].son[i];
}
}
}
void Deal_matchstring()
{
int x;
scanf("%d",&x);
scanf("%s",s+1);
fo(i,1,x)
if (!exist[s[i]-'a'])
{
exist[s[i]-'a'] = 1;
a[++M] = s[i] - 'a';
}
}
void DP()
{
f[0][0][0] = 1;
fo(i,0,N-1)
fo(j,0,tot)
fo(k,0,(1<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Swift 연습 Swift3에서 문자열을 정수로 변환하는 방법Swift3에서 문자열을 정수로 변환하는 방법 Swift3.swift Swift3.log 그럼 실패하지 않는 방법 Swift3.swift Swift3.log Swift1.x에서는, ""12345""라고 하는 정수를 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.