Untitled

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
 
using namespace std;
 
const int MAXCHARLEN = 256;
const int MAXLEN = 100;

struct node
{
    int cur;
    int prev;
} modelSet[MAXLEN][MAXLEN];
 
struct nextNode
{
    int state;
    int character;
} nextTable[MAXCHARLEN];

struct outputNode
{
    int state;
    char str[MAXLEN];
    bool available;
} output[MAXCHARLEN];
 
queue<int>q;
int book[MAXCHARLEN];
int base[MAXCHARLEN];
int checkTable[MAXCHARLEN];
int failTable[MAXCHARLEN];
int currentState=0;
int fatherState=0;
 
int readyToInsert[MAXCHARLEN];
int globalIndex=0;
int curNodeNum=0;
int nextNodeNum=0;
int inputNum;
char input[MAXLEN][MAXLEN];
int currentPos;
 
void buildTable();
int gotoFunc(int state,int c);
void buildFailTable();
void buildOutputTable();
 

int main()
{
    freopen("input.txt","r",stdin);
    memset(input,0,sizeof(input));
    scanf("%d",&inputNum);
    int rowLen;
    int maxRowLen=-1;
    for(int i=0; i<inputNum; i++)
    {
        scanf(" %s",input[i]);
        rowLen=strlen(input[i]);
        if(rowLen>maxRowLen) maxRowLen=rowLen;
        for(int j=0; j<rowLen; j++)
        {
            modelSet[i][j].cur=input[i][j];
            if(!j) modelSet[i][j].prev=0;
            else modelSet[i][j].prev=input[i][j-1];
        }
    }
 
    memset(book,0,sizeof(book));
    for(int i=0; i<inputNum; i++)
    {
        book[modelSet[i][0].cur]=1;
    }
    for(int j=0; j<MAXCHARLEN; j++)
    {
        if(book[j])
        {
            q.push(j);
            readyToInsert[globalIndex++]=j;
        }
    }
    curNodeNum=globalIndex;
    buildTable();
 
    int k=1;
    while(!q.empty())
    {
        memset(book,0,sizeof(book));
        int qhead=q.front();
        q.pop();
        curNodeNum--;
        for(int i=0; i<inputNum; i++)
        {
            if(modelSet[i][k].cur==0) continue;
            if(qhead==modelSet[i][k].prev)
            {
                book[modelSet[i][k].cur]=1;
            }
        }
        for(int j=0; j<MAXCHARLEN; j++)
        {
            if(book[j])
            {
                q.push(j);
                readyToInsert[globalIndex++]=j;
                nextNodeNum++;
            }
        }
        buildTable();
        if(!curNodeNum)
        {
            curNodeNum=nextNodeNum;
            k++;
            nextNodeNum=0;
        }
    }
    cout << "checkTable" << endl;
    for(int i=0; i<=12; i++)
    {
        cout << checkTable[i] << " ";
    }
    cout << endl << "nextTable" << endl;
    for(int i=0; i<=12; i++)
    {
        cout << nextTable[i].state << " ";
    }
    cout << endl << "baseTable" << endl;
    for(int i=0; i<=currentState; i++)
    {
        cout << base[i] << " ";
    }
    buildFailTable();
    cout << endl << "failTable" << endl;
    for(int i=0; i<=currentState; i++)
    {
        cout << failTable[i] << " ";
    }
    buildOutputTable();
    return 0;
}
 
void buildTable()
{
    if(!globalIndex)return;
    int offset=1;
    for(; offset<MAXCHARLEN; offset++)
    {
        if(!nextTable[offset].state) break;
    }
    base[fatherState]=offset-(readyToInsert[0]);
    bool flag=1;
    while(flag)
    {
        int p=0;
        for(; p<globalIndex; p++)
        {
            if((nextTable[base[fatherState]+readyToInsert[p]].state)!=0) break;
        }
        if(p==globalIndex) flag=0;
        else base[fatherState]++;
    }
    for(int i=0; i<globalIndex; i++)
    {
        nextTable[base[fatherState]+readyToInsert[i]].state=++currentState;
        nextTable[base[fatherState]+readyToInsert[i]].character=readyToInsert[i];
        checkTable[currentState]=fatherState;
    }
 
    memset(readyToInsert,0,sizeof(0));
    globalIndex=0;
    fatherState++;
}
 
void buildFailTable()
{
    for(int i=0; i<=currentState; i++)
    {
        if(!checkTable[i]) continue;
        else
        {
            for(int j=0; j<MAXCHARLEN; j++)
            {
                if(nextTable[j].state==i)
                {
                    failTable[i]=gotoFunc(failTable[checkTable[i]],nextTable[j].character);
                    break;
                }
            }
        }
    }
}
 
int gotoFunc(int state,int c)
{
    int t=nextTable[base[state]+c].state;
    if(checkTable[t]==state) return t;
    else if(state==0) return 0;
    else {
        return gotoFunc(failTable[state],c);
    }
}
 
void buildOutputTable()
{
    char keng1[MAXCHARLEN];
    for(int i=1; i<=currentState; i++)
    {
        memset(keng1,0,sizeof(keng1));
        output[i].state=i;
        int temp=i;
        int num=0;
        while(temp)
        {
            for(int j=0; j<MAXCHARLEN; j++)
            {
                if(temp==nextTable[j].state)
                {
                    keng1[num++]=nextTable[j].character;
                    break;
                }
            }
            temp=checkTable[temp];
        }
        int k=0;
        for(int p=num-1; p>=0; p--)
        {
            output[i].str[k++]=keng1[p];
        }
        for(int q=0; q<inputNum; q++)
        {
            if(!strcmp(input[q],output[i].str))
            {
                output[i].available=1;
                break;
            }
        }
    }
}