문자열 KMP Trie AC 자동 접미사 배열

접미사 배열 도 보고 있 습 니 다. 나 수 건 신 우의 수업 은 정말 기 쁩 니 다.
오늘 KMP, Trie, AC 자동 동기 와 접미사 배열 을 포함 한 문자열 연습 을 했 습 니 다.
A. Oulipo
POJ 인 것 같은 데 예전 에 해 봤 어 요.그냥 KMP 물 로 지 나 갔 어 요.
B. 통계 문제
HDU 의 것 이 죠? 문 제 는 다른 문자열 접두사 의 개 수 를 구 하 는 것 입 니 다. 바로 Trie 로 하 는 것 입 니 다.

struct trie{
    int count ;
    struct trie *next[26] ;
    trie(){
        mem(next,0) ;
        count = 0 ;
    }
} ;
trie *root = 0 ;
void build(char *a){
    int l = strlen(a) ;
    trie *p = root ;
    trie *temp = 0 ;
    for (int i = 0 ; i < l ;i ++ ){
        int tt = a[i] - 'a' ;
        if(p -> next[tt] == 0){
            temp = new trie ;
            p -> next[tt] = temp ;
        }
        p = p -> next[tt] ;
        p -> count ++ ;
    }
}

int search(char *a){
    int l = strlen(a) ;
    trie *p = root ;
    bool flag = 0 ;
    for (int i = 0 ; i < l ; i ++ ){
        int tt = a[i] - 'a' ;
        if(p -> next[tt] == 0){
            flag = 1 ;
            break ;
        }
        p = p -> next[tt] ;
    }
    if(flag)return 0 ;
    return p -> count ;
}
int main() {
    char a[11111] ;
    root = new trie ;
    int d = 5 ;
    while(gets(a)){
        int l = strlen(a) ;
        if(!l)break ;
        build(a) ;
    }
    while(cin >> a){
        cout << search(a) << endl;
    }
    return 0 ;
}

C. Keywords Search
HDU 문 제 는 N 번 KMP, TLE, N 번 트 리, MLE (순수 엔 터 테 인 먼 트..), AC 자동 동기 A 로 세 가지 방법 을 사 용 했 습 니 다.
제목 은 대상 문자열 에 몇 번 이나 나 왔 는 지 물 어 보 는 문자열 을 주 는 것 이다.
AC 자동 학습 과목 이 인터넷 에 많아 서 저 는 AC 자동 동기 에 대한 이 해 를 말씀 드 리 겠 습 니 다.
사실 AC 자동 동 기 는 KMP + Trie 인 데, 그의 페 일 지침 은 KMP 의 next 배열 과 같은 역할 을 한다.
Fail 포인 터 는 현재 노드 자모의 마지막 에 나타 난 이 자모의 위 치 를 가리 키 며, 없 으 면 root 를 가리킨다.
구체 적 으로 는 신 우 블 로 그 를 보 세 요.신우 블 로그

//HDU 2222

struct node {
    node *fail ;
    node *next[26] ;
    int count ;
    node() {
        fail = 0 ;
        count = 0 ;
        mem(next , 0) ;
    }
}*qe[500005] ;
node *root = 0 ;
//insert a[] .
void insert(char *a) {
    node *p = root ;
    int l = strlen(a) ;
    for (int i = 0 ; i < l ; i ++ ) {
        int tt = a[i] - 'a' ;
        if(p -> next[tt] == 0) {
            p -> next[tt] = new node() ;
        }
        p = p -> next[tt] ;
    }
    p -> count ++ ;
}
//build *fail .
void build() {
    root -> fail = 0 ;
    int h = 0 , t = 0 ;
    qe[h ++ ] = root ;
    while(h > t) {
        node *temp = qe[t ++ ] ;
        node *p = 0 ;
        for (int i = 0 ; i < 26 ; i ++ ) {
            if(temp -> next[i] != 0) {
                if(temp == root)temp -> next[i] -> fail = root ;
                else {
                    p = temp -> fail ;
                    while(p != 0) {
                        if(p -> next[i] != 0) {
                            temp -> next[i] -> fail = p -> next[i] ;//    
                            break ;
                        }
                        p = p -> fail ;
                    }
                    if(p == 0)temp -> next[i] -> fail = root ;//     ，  fail  root
                }
                qe[h ++ ] = temp -> next[i] ;
            }
        }
    }
}

int search(char *a) {
    int l = strlen(a) ;
    node *p = root ;
    int ans = 0 ;
    for (int i = 0  ; i < l ; i ++ ) {
        int tt = a[i] - 'a' ;
        while(p -> next[tt] == 0 && p != root)p = p -> fail ;
        p = p -> next[tt] ;
        p = (p == 0) ? root : p ;
        node *temp = p ;
        while(temp != root && temp -> count != -1) {
            ans += temp -> count ;
            temp -> count = -1 ;
            temp = temp -> fail ;
        }
    }
    return ans ;
}
char aa[55] ;
char bb[1111111] ;
int main() {
    int T ;
    cin >> T ;
    while (T -- ) {
        int n ;
        root = new node() ;
        cin >> n ;
        for (int i = 0 ; i < n ; i ++ ) {
            scanf("%s",aa) ;
            insert(aa) ;
        }
        build() ;
        scanf("%s",bb) ;
        cout << search(bb) << endl;
    }
    return 0 ;
}

D. Longest Common Substring
문 제 는 두 개의 꼬치 를 주 고 가장 긴 공공 문자열 의 길 이 를 묻 는 것 이다.
접미사 배열, 나 수 건 신소 의 수업 을 보고 있 습 니 다.
두 문자열 의 가장 긴 공공 문자열 의 길 이 를 찾 습 니 다.우선 두 문자열 을 연결 하고 중간 에 나타 나 지 않 은 문자 로 연결 합 니 다.
그리고 height 배열 의 특성 을 이용 하여 서로 다른 문자열 에 있 는 접미사 의 가장 큰 height 를 찾 을 수 있 습 니 다.
우리 height 알 아 요. sa [i - 1] 과 sa [i] 의 가장 긴 공공 접두사.
그러면 우 리 는 사 [i - 1] 와 사 [i] 가 서로 다른 문자열 에 있 는 문자열 만 찾 으 면 된다.
구체 적 인 판단 은 코드 를 보십시오.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include