HUNAN 11187 이모 티 콘: -) (ac 자동 동기 + 욕심)

제목:
n 개의 이모 티 콘 을 드 립 니 다. 현재 txt 를 드 립 니 다. txt 에 대응 하 는 자 모 를 빈 칸 으로 바 꾸 어 txt 에 어떤 이모 티 콘 을 포함 하지 않도록 해 야 합 니 다.최소 조작 수 를 구하 다.
문제 풀이:
dp 는 반드시 끊 을 것 입 니 다. 메모리 나 시간의 소모 에 관 계 없 이 모두 끊 을 것 입 니 다.
그럼 욕심 으로 할 수 있 을 지 생각해 봐 야 지.
번 에 따 르 면 저도 이런 글 에 대해 이모 티 콘 이 나 오 면 몇 가지 상황 이 있 습 니 다.
1. 각 이모 티 콘 이 따로 분리 되 어 있 습 니 다. 이것 은 쉽게 말 하면 ans + 와 일치 하 는 것 을 직접 만 날 수 있 습 니 다.
2. 만약 에 두 개 또는 여러 개가 겹 치면 예 를 들 어 a, b, c 가 겹 친다.
(1) a, b, c 가 서로 겹 치면 a 가 가장 많이 겹 치 는 부분 임 이 분명 하 다. 그러면 a 의 끝 을 수정 하면 된다.
(2) a, b, 중첩, c, b 도 중첩 되 지만 a, c 는 중첩 되 지 않 습 니 다. 이런 상황 은 a 의 끝 을 먼저 수정 합 니 다. 그러면 b 의 부분 은 이미 이모 티 콘 이 아 닙 니 다. 수정 할 필요 가 없습니다!그러면 지금 이 상황 은 1 의 상황 이 되 었 고 여러 개의 꼬치 가 분리 되 었 습 니 다. b 는 이미 이모 티 콘 이 아니 기 때문에 c 는 단독 입 니 다.
3. 관 계 를 포함 합 니 다. 이것 도 좋 습 니 다. 포 함 된 문자열 의 끝 을 선택 하여 수정 하 는 것 이 분명 합 니 다.
욕심 의 증명 이 었 습 니 다.그래서 매번 일치 하면 바로 뿌리 로 돌아 갑 니 다.
왜 자꾸 RE 인지 모 르 겠 어 요. 이상해 요.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define B(x) (1<<(x))
//typedef __int64 ll;
//typedef unsigned __int64 Ull;
const int oo=0x3f3f3f3f;
//const ll OO=1LL<<61;
//const Ull MOD=1000000;
const int maxn=30;
const int SIZE=3003;
const int type=256;
char str[maxn];

struct ACautomaton
{
    int next[SIZE][type],fail[SIZE],word[SIZE];
    int cnt,root;

    int newNode()
    {
        for(int i=0;i<type;i++)
            next[cnt][i]=-1;
        word[cnt++]=0;
        return cnt-1;
    }

    void Init()
    {
        cnt=0;
        root=newNode();
    }

    void Insert(char buff[])
    {
        int now=root;
        for(int i=0,k;buff[i];i++)
        {
            k=buff[i];
            if(next[now][k]==-1)
                next[now][k]=newNode();
            now=next[now][k];
        }
        word[now]=1;
    }

    void build()
    {
        fail[root]=root;
        int now=root;
        queue<int>Q;
        for(int i=0;i<type;i++)
        {
            if(next[now][i]==-1)
                next[now][i]=root;
            else
            {
                fail[next[now][i]]=root;
                Q.push(next[now][i]);
            }
        }
        while(!Q.empty())
        {
            now=Q.front();
            Q.pop();
            if(word[fail[now]]) word[now]=1;
            for(int i=0;i<type;i++)
            {
                if(next[now][i]==-1)
                    next[now][i]=next[fail[now]][i];
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
            }
        }
    }

    int greed()
    {
        int ans=0;
        int now=root,temp;
        char ch;
        while((ch=getchar())!='
')
        {
            if(ch==' ')
            {
                now=root;
                continue;
            }
            now=next[now][ch];
            temp=now;
            while(temp!=root)
            {
                if(temp==-1)break;
                if(word[temp])
                {
                    ans++;
                    now=root;
                    break;
                }
                temp=fail[temp];
            }
        }
        return ans;
    }

};
ACautomaton ac;

int main()
{
    int n,m,ans;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        ac.Init();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str);
            ac.Insert(str);
        }
        ac.build();
        ans=0;
        for(int i=1;i<=m;i++)
        {
            getchar();
            ans+=ac.greed();///  ，      ，       
        }
        printf("%d
",ans);
    }
    return 0;
}
/**
*/