AC 자동 동기 템 플 릿 문 제 는 자신의 손 으로 템 플 릿 을 한 번 두 드 렸 다.
짝 짓 기 변 을 추가 할 때 각 노드 의 26 개의 알파벳 변 링크 의 하위 노드 를 한 번 훑 어 본다. 만약 에 결점 이 존재 한다 면 이 하위 노드 의 짝 짓 기 변 은 바로 주 결점 의 짝 짓 기 변 에 대응 하 는 노드 이다.
만약 에 결점 이 존재 하지 않 는 다 면 이 결점 은 주 결점 의 어 울 리 지 않 는 변 에 대응 하 는 결점 링크 의 하위 노드 에 직접 연 결 됩 니 다.
AC 자동 동기 가 너무 어려워...QAQ
11885512
2014-10-16 16:22:43
Accepted
2222
687MS
26688K
2772 B
G++
KinderRiven
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 555555;
const int maxn_sign = 26;
const int maxd = 1111111;
int root;
struct Trie{ //AC
int tr[maxn][maxn_sign];//Trie
int fail[maxn]; //
int val[maxn];
int sz; //
int counts;
int index(int c){
if(c >= 'a' && c <= 'z')
return c - 'a';
if(c >= 'A' && c <= 'Z')
return c - 'A';
}
void init(){ //
sz = 0; val[0] = 0; counts = 0;
for(int i = 0; i < 26; i++) tr[0][i] = -1;
}
int newnode(){ //
val[sz] = 0;
for(int i = 0; i < 26; i++) tr[sz][i] = -1;
sz ++;
return sz - 1;
}
void insert(char *str){
int u = 0,n = strlen(str);
for(int i = 0; i < n; i++){
int e = index(str[i]);
if(tr[u][e] == -1){ //
int d = newnode();
tr[u][e] = d;
}
u = tr[u][e];
}
val[u] ++;
}
void buildfail(){
queueq;
fail[root] = root; //
for(int i = 0; i < 26; i++){
if(tr[root][i] == -1)
tr[root][i] = root;
else{
q.push(tr[root][i]);
fail[tr[root][i]] = root;
}
}
while(!q.empty()){
int node = q.front(); q.pop();
for(int i = 0; i < 26; i++){
if(tr[node][i] == -1){
tr[node][i] = tr[fail[node]][i];
}
else{
fail[tr[node][i]] = tr[fail[node]][i];
q.push(tr[node][i]);
}
}
}
}
void triecount(char *str){
int L = strlen(str);
int u = 0;
for(int i = 0; i < L;i ++){
u = tr[u][index(str[i])];
int temp = u;
while(temp != root){
counts += val[temp];
val[temp] = 0;
temp = fail[temp];
}
}
}
};
Trie ac;
char s[maxd];
int main(){
int T;
scanf("%d",&T);
while(T--){
ac.init();
int n;
root = ac.newnode();
char str[55];
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%s",str);
ac.insert(str);
}
scanf("%s",s);
ac.buildfail();
ac.triecount(s);
printf("%d
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전
Udemy 에서 공부 한 것을 중얼거린다
Chapter3【Integer Reversal】
(예)
문자열로 숫자를 반전 (toString, split, reverse, join)
인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
