UVALIVE 5792 Trie + 통계

제목: 두 가지 꼬치 를 드 리 겠 습 니 다. 하 나 는 접두사 가 될 수 있 고 하 나 는 접두사 가 될 수 있 습 니 다. 두 가지 꼬치 를 합치 면 모두 몇 가지 조합 이 있 는 지 물 어보 세 요.겹 치지 않 았 습 니 다.
사고: 우 리 는 먼저 두 개의 문자열 을 사전 트 리 에 삽입 하고 접미사 문자열 에 대해 우 리 는 반대로 삽입 한 다음 에 모든 문자 에 대응 하 는 접미사 의 개 수 를 처리 합 니 다.
우 리 는 그룹의 꼬치 를 보 겠 습 니 다. c = a + b.이 c 는 여러 가지 조합 이 있 을 수 있 지만, 우리 가 a 를 가장 많이 취하 면, 이렇게 계산 하 는 것 이 유일한 것 이다.a 가 가장 큰 것 은 a 가 이 접두사 의 마지막 자모 라 는 것 을 찾 으 면 a 가 가장 큰 것 이다.
이것 은 a 가 마지막 자모 인 상황 에 대응 하 는 것 이다. 만약 에 a 뒤에 알파벳 이 있다 면 우 리 는 접미사 가 존재 하 는 지 찾 을 수 있다. 그 는 알파벳 이 하나 밖 에 없다. 그러면 우 리 는 그 를 a 의 뒤에 받 을 수 있다.
그래서 대응 하 는 접두사 a 는 우 리 는 이 두 가지 상황 으로 나 누 어 고려 하면 된다.
롱 롱 사용 에 주의 하 세 요.

#define N 311111
ll ans = 0 ;
ll sum[30] ;
int end[30] ;
struct TT {
    int num ;
    int T[N][26] ;

    TT() {
        num = 0 ;
    }
    void INIT() {
        mem(T[0], -1) ;
        num = 0 ;
    }
    void init(int x) {
        mem(T[x] , -1) ;
    }
    void insert(char *s) {
        int l = strlen(s) ;
        int now = 0 ;
        for (int i = 0 ; i < l ; i ++ ) {
            int a = s[i] - 'a' ;
            if(T[now][a] == -1) {
                T[now][a] = ++ num ;
                init(num) ;
            }
            now = T[now][a] ;
        }
    }
    void cal(int now) {
        for (int i = 0 ; i < 26 ; i ++ ) {
            if(T[now][i] == -1) {
                ans += sum[i] ;
            } else {
                if(end[i])
                    ans ++ ;
                cal(T[now][i]) ;
            }
        }
    }
    int fk(int now) {
        for (int i = 0 ; i < 26 ; i ++ ) {
            if(T[now][i] != -1) {
                sum[i] ++ ;
                fk(T[now][i]) ;
            }
        }
    }
} sufTree , preTree ;

char s[1111] , p[1111] ;
int P , S ;
int main() {
    while(cin >> P >> S, (P + S)) {
        sufTree.INIT() ;
        preTree.INIT() ;
        for (int i = 0 ; i < P ; i ++ ) {
            scanf("%s",p) ;
            preTree.insert(p) ;
        }
        for (int i = 0 ; i < S ; i ++ ) {
            scanf("%s",s) ;int l = strlen(s) ;
            reverse(s , s + l) ;
            sufTree.insert(s) ;
        }
        mem(sum , 0) ;
        mem(end , 0) ;
        ans = 0 ;
        sufTree.fk(0) ;
        for (int i = 0 ; i < 26 ; i ++ )if(sufTree.T[0][i] != -1)end[i] = 1 ;
        for (int i = 0 ; i < 26 ; i ++ )if(preTree.T[0][i] != -1)preTree.cal(preTree.T[0][i]) ;
        printf("%lld
",ans) ;
    }
    return 0 ;
}