UVa:11732 strcmp() Anyone?

두 시간 넘 게 고생 하 다가 마침내 이 문 제 를 주 었 다.
처음에 생각 나 서 다 진 타이어 라 고 썼 는데 시간 이 초과 되 었 습 니 다.더 이상 작 을 수 없 는 알고리즘 인 것 같 습 니 다. 나중에 memset 만 있 으 면 시간 이 오래 걸 리 는 것 을 발 견 했 습 니 다. 그래서 새로운 노드 를 열 때마다 memset 로 바 꾸 었 고 읽 기 출력 외 장 도 추 가 했 습 니 다. 결 과 는 시간 을 초과 하 였 습 니 다.나중에 인터넷 문제 풀이 에 왼쪽 아들 오른쪽 형제 표현법 으로 하 겠 다 고 해서 '1.7sAC' 라 고 썼 습 니 다.
다 차 적 표기 법 은 아래 표 시 를 직접 이용 하여 대응 하 는 문 자 를 표시 하기 때문에 공간 낭비 가 비교적 심각 하지만 어떤 결점 을 찾 아야 하 는 아이의 결점 은 O (1) 이다.
두 갈래 의 문법 은 매번 비교 검색 을 통 해 대응 하 는 문 자 를 찾 을 수 있 기 때문에 낭비 할 공간 이 없 지만 시간 이 많이 걸린다.
다 차 와 이 차 의 표기 법 은 마치 인접 행렬 과 인접 표 와 같다.
이 문 제 는 다 차 표기 법 이 시간 을 초과 할 수 있 습 니 다. 아마 배열 이 너무 크게 열 렸 을 것 입 니 다. 매번 memset 이 시간 을 초과 할 때마다 (전에 쓴 몇 개의 tire 코드 를 생각 할 때 도 느 립 니 다. 아마도 이 때 문 일 것 입 니 다)
왼쪽 아들 오른쪽 형제의 글씨 로, 원래 케이스 마다 모든 배열 memset 을 한 번 씩 놓 쳤 는데, 결 과 는 1.8s 를 달 렸 다. 나중에 이것 을 고 쳐 서, 나 무 를 지 을 때마다 모든 결산 점 을 비우 고, 0.8s 로 바 꾸 었 다.
이 문제 의 사 고 는 나 무 를 지 을 때마다 모든 노드 문자 가 나타 나 는 횟수 를 고려 하고 현재 노드 전에 나타 난 횟수 와 비교 해 야 한다. 여기 서 두 번 비교 하고 아버지 와 노드 를 비교 해 야 한다. 여 기 는 아버지 노드 에서 현재 노드 의 그 부분 을 없 애고 한 번 만 비교 해 야 한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
#define INF 200000000
#define MOD 20071027
#define MAXN 4000*1005
using namespace std;
ll ans;
struct Tire
{
    int child[MAXN],next[MAXN],val[MAXN];
    char str[MAXN];
    int sz;
    void Init()
    {
        sz=1;
        child[0]=0;
        next[0]=0;
        val[0]=0;
    }
    void Insert(char *word)
    {
        int u=0,v;
        val[u]++;
        for(int i=0; word[i]; ++i)
        {
            bool ok=false;
            for(v=child[u]; v; v=next[v])
            {
                if(str[v]==word[i])
                {
                    ok=true;
                    break;
                }
            }
            if(!ok)
            {
                str[sz]=word[i];
                val[sz]=0;
                child[sz]=0;
                v=sz++;
                next[v]=child[u];
                child[u]=v;
            }
            ans+=val[v]*2;
            val[v]++;
            ans+=val[u]-val[v];
            u=v;
        }
    }
};
Tire tree;
char word[1005];
int main()
{
    int n,kase=0;
    while(scanf("%d",&n)!=EOF&&n)
    {
        getchar();
        ans=0;
        tree.Init();
        for(int i=0; i<n; ++i)
        {
            int j=0;
            while(word[j]=getchar())
            {
                if(word[j]=='
') break;
                j++;
            }
            word[j]='#';
            word[j+1]=0;
            tree.Insert(word);
        }
        printf("Case %d: %lld
",++kase,ans);
    }
    return 0;
}