ZOJ 3228 Searching the String AC 자동 동기 의 중복 일치 하지 않 음

6344 단어 데이터 구조
이 판단 방법 은 정말 생각 지도 못 했다...
S 에서 M 과 일치 하 는 경우 M 의 지난번 일치 하 는 위치 pre 가 이번 일치 하 는 위치 now 만족 now - pre > = M. length 이면 1 을 추가 합 니 다.
이 판단 은 너무 뛰 어 요.
#include 
#include
#include
#include
#include
#include
#include
#include
#include 
#include 
#include 

#define LL long long
#define ULL unsigned long long

using namespace std;

const int MAXS = 26,MAXN  = 600010;
const int MATN = 70;

struct MAT
{
    int row,col;
    ULL mat[MATN][MATN];

    void Init(int R,int C,int val)
    {
        row = R,col = C;

        for(int i = 1;i <= row; ++i)
            for(int j = 1;j <= col; ++j)
                    mat[i][j] = (i == j ? val : 0);
    }

    MAT Multi(MAT c,LL MOD)
    {
        MAT tmp;
        tmp.Init(this->row,c.col,0);

        int i,j,k;
       for(k = 1;k <= this->col; ++k)
            for(i = 1;i <= tmp.row; ++i)
                for(j = 1;j <= tmp.col; ++j)
                    tmp.mat[i][j] += (this->mat[i][k]*c.mat[k][j]);

        return tmp;
    }

    MAT Quick(LL n,LL MOD)
    {
        MAT res,tmp = *this;

        res.Init(row,col,1);

        while(n)
        {
            if(n&1)
                res = res.Multi(tmp,MOD);
            tmp = tmp.Multi(tmp,MOD);
            n >>= 1;
        }

        return res;
    }

    void Output()
    {
        cout< q;

int anw[100010];

int pre[100010];

struct QUERY
{
    int y;
    char s[8];
    int len;
}que[100100];

struct ACautomaton
{
    int Top,root;

    int  Creat()
    {
        memset(st[Top].next,-1,sizeof(st[Top].next));
        st[Top].flag = 0;
        st[Top].fail = -1;
        return Top++;
    }

    void Init()
    {
        Top = 0;
        root = Creat();
    }

    inline int CalIndex(int c)
    {
        return c-'a';
    }

    void Insert(char *s,int ty)
    {
        int i = 0,tr = root,tmp;

        while(s[i] != '\0')
        {
            tmp = CalIndex(s[i]);
            if(st[tr].next[tmp] == -1)
                st[tr].next[tmp] = Creat();
            tr = st[tr].next[tmp],++i;
        }
        st[tr].flag = ty;
    }

    void GetFail()
    {
        st[root].fail = -1;
        q.push(root);

        int f,t;

        while(q.empty() == false)
        {
            f = q.front();
            q.pop();

            for(int i = 0; i < MAXS; ++i)
            {
                if(st[f].next[i] != -1)
                {
                    t = st[f].fail;

                    while(t != -1 &&  st[t].next[i] == -1)
                        t = st[t].fail;

                    if(t == -1)
                        st[st[f].next[i]].fail = root;
                    else
                        st[st[f].next[i]].fail = st[t].next[i];

                    q.push(st[f].next[i]);
                }
            }
        }
    }

    int OverLapMatch(char *s)
    {
        int i ,tr = root,tmp;
        int ans = 0;
        for(i = 0; s[i] != '\0'; ++i)
        {
            tmp = CalIndex(s[i]);

            while(tr != -1 && st[tr].next[tmp] == -1 )
                tr = st[tr].fail;
            if(tr == -1)
            {
                tr = root;
                continue;
            }

            tr = st[tr].next[tmp];

            tmp = tr;

            while(tmp != root && st[tmp].flag != -1)
            {
                if(st[tmp].flag)
                    ans++,anw[st[tmp].flag]++;
                tmp = st[tmp].fail;
            }
        }
        return ans;
    }

    int NoOverLapMatch(char *s)
    {
        int i ,tr = root,tmp;
        int ans = 0;
        for(i = 0; s[i] != '\0'; ++i)
        {
            tmp = CalIndex(s[i]);

            while(tr != -1 && st[tr].next[tmp] == -1 )
                tr = st[tr].fail;

            if(tr == -1)
            {
                tr = root;
                continue;
            }

            tr = st[tr].next[tmp];

            tmp = tr;

            while(tmp != root && st[tmp].flag != -1)
            {
                if(st[tmp].flag)
                {
                    if(i-pre[st[tmp].flag] >= que[st[tmp].flag].len)
                    ans++,anw[st[tmp].flag]++,pre[st[tmp].flag] = i;
                }
                tmp = st[tmp].fail;
            }
        }
        return ans;
    }
};

char s[100010];

map M;
map::iterator it;

int main()
{
   // freopen("data1.in","r",stdin);
    int n,i;
    ACautomaton AC;

    int icase =1;

    while(scanf("%s",s) != EOF)
    {
        scanf("%d",&n);

        for(i = 1;i <= n; ++i)
            scanf("%d %s",&que[i].y,que[i].s);

        for(i = 1;i <= n; ++i)
            que[i].len = strlen(que[i].s);

        memset(pre,-1,sizeof(pre));
        memset(anw,0,sizeof(anw));

        AC.Init();

        for(i = 1;i <= n; ++i)
        {
            if(que[i].y == 0)
                AC.Insert(que[i].s,i);
        }

        AC.GetFail();

        AC.OverLapMatch(s);

        M.clear();

        for(i = n;i >= 1; --i)
        {
            if(que[i].y == 0)
            {
                it = M.find(que[i].s);

                if(it != M.end())
                    anw[i] = anw[it->second];
                else
                    M.insert(pair(que[i].s,i));
            }
        }

        AC.Init();

        for(i = 1;i <= n; ++i)
        {
            if(que[i].y == 1)
                AC.Insert(que[i].s,i);
        }

        AC.GetFail();

        AC.NoOverLapMatch(s);

        M.clear();

        for(i = n;i >= 1; --i)
        {
            if(que[i].y == 1)
            {
                it = M.find(que[i].s);

                if(it != M.end())
                    anw[i] = anw[it->second];
                else
                    M.insert(pair(que[i].s,i));
            }
        }
        printf("Case %d
",icase++);
        for(i = 1;i <= n; ++i)
            printf("%d
",anw[i]);
        puts("");
    }

    return 0;
}
Python에서 슬라이싱이 아닌 Catch-All Unpacking을 사용해야 하는 이유
JS 문자열 상용 기초

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage