2017.3.15 심사(황금) 사고 기록

이 문제는 귀속의 성질을 만족시키기 때문에 ac자동기+창고로 처리할 수 있다
그런데 알을 합치면 틀림없이 점이 하나 있는데,
  #include #include using namespace std; #include struct ac {     ac *fail;      ac * xia[26];     int ci,ceng;     ac() {          fail = NULL;         ci= 0;         memset(xia, NULL, sizeof (xia));     } } *q[10000001],*root; int hehe,changdu[500001],i,huhu;  char s1[500001]; int zhen1,zhen2;  void insert(char *str, ac *root) {     ac *p = root;     int i = 0, zimu;     while (str[i]) {         zimu = str[i] - 'a';         if (p->xia[zimu] == NULL)         {             p->xia[zimu] = new ac();         }         p = p->xia[zimu];         i++;     }     p->ci=++hehe; } void shipei(ac *root) {     int i;     root->fail = NULL;     q[zhen1++] = root;     while (zhen1 != zhen2) {         ac *now = q[zhen2++];         ac *p = NULL;         for (i = 0; i < 26; i++) {             if (now->xia[i] != NULL) {                 if (now == root)                     now->xia[i]->fail = root;                 else {                     p = now->fail;                     while (p != NULL) {                         if (p->xia[i] != NULL) {                             now->xia[i]->fail = p->xia[i];                             break;                         }                         p = p->fail;                     }                     if (p == NULL)                         now->xia[i]->fail = root;                 }                 q[zhen1++] = now->xia[i];             }         }              } } int zhan[500005],zhen; char ystr[500005]; int zimu; ac *tui(ac *now) {       zimu = ystr[i] - 'a';           while (now->xia[zimu] == NULL && now != root) now = now->fail;         now = now->xia[zimu];         if(now==NULL)now=root;         return now; } ac *f[500008]; void work() {    //cout<    //ac *shang=root;     zhan[0]=500005;     int *zhen=zhan;          f[500005]=root;int fin=strlen(ystr);          for(i=0;i     {        ++zhen;  *zhen=i;                f[i]=tui(f[*(zhen-1)]);         if(f[i]->ci)zhen-=changdu[f[i]->ci];     }            for(int *i=zhan+1;i!=zhen;i++)     {     printf("%c",ystr[*i]);}     printf("%c",ystr[*zhen]); } int main() {     int n, t;     scanf("%s", ystr);         zhen1 = zhen2 = 0;       root = new ac();         scanf("%d", &n);                        for(i=1;i<=n;i++){             scanf("%s",s1);             insert(s1, root);             changdu[i]=strlen(s1);         }      //  cout<         shipei(root);                 //cout<       work();             return 0; }
그날 오후가 드디어 지나고,
lych 문제를 많이 풀었기 때문에 드디어 검색을 응용했습니다.

#include
#include
using namespace std;
#include


struct ac {
    ac *fail; 
    ac * xia[26];
    int ci,ceng; 


   ac() { 
        fail = NULL;
        ci= 0;
        memset(xia, NULL, sizeof (xia));
    }
} *q[500001],*root;
int hehe,changdu[100001],i,huhu; 
char s1[100001];
int zhen1,zhen2; 


void insert(char *str, ac *root) {
    ac *p = root;
    int i = 0, zimu;
    while (str[i]) {
        zimu = str[i] - 'a';
        if (p->xia[zimu] == NULL)
        {
            p->xia[zimu] = new ac();
        }
        p = p->xia[zimu];
        i++;
    }
    p->ci=++hehe;
}




void shipei(ac *root) {
    int i;
    root->fail = NULL;
    q[zhen1++] = root;
    while (zhen1 != zhen2) {
        ac *now = q[zhen2++];
        ac *p = NULL;
        for (i = 0; i < 26; i++) {
            if (now->xia[i] != NULL) {
                if (now == root)
                    now->xia[i]->fail = root;
                else {
                    p = now->fail;
                    while (p != NULL) {
                        if (p->xia[i] != NULL) {
                            now->xia[i]->fail = p->xia[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if (p == NULL)
                        now->xia[i]->fail = root;
                }
                q[zhen1++] = now->xia[i];
            }
        }
        
    }
}
ac *jisou[200001][27];
int zhan[100009],zhen;
char ystr[100005];
int zimu;
ac *tui(ac *now)
{      int jishu=0;
zimu = ystr[i] - 'a';
   if(zhan[zhen-1]>=0&&jisou[zhan[zhen-1]][zimu]!=NULL)return jisou[zhan[zhen-1]][zimu];
      
    while (now->xia[zimu] == NULL && now != root) now = now->fail,++jishu;
        now = now->xia[zimu];
        if(now==NULL)now=root;
       if(zhan[zhen-1]>=0) jisou[zhan[zhen-1]][zimu]=now;
        
        //if(jishu>2)cout<ci)
       {
           zhen-=changdu[f[i]->ci];
       }
        
    }
    
    
    for(i=1;i<=zhen;i++)
    {
        printf("%c",ystr[zhan[i]]);
        
    }
    
}


int main() {
//	freopen("censor.in","r",stdin);
//	freopen("censor.out","w",stdout);
    int n, t;
    scanf("%s", ystr);
        zhen1 = zhen2 = 0;
      root = new ac();
        scanf("%d", &n);
     
        
        for(i=1;i<=n;i++){
            scanf("%s",s1);
            insert(s1, root);
            changdu[i]=strlen(s1);
        }
     //   cout<