fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <fstream>
  9. #include <vector>
  10. #include <queue>
  11. #include <deque>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <complex>
  16. #include <string>
  17. #define REP(i,j) for(int i=1;i<=j;++i)
  18. #define REPI(i,j,k) for(int i=j;i<=k;++i)
  19. #define REPD(i,j) for(int i=j;0<i;--i)
  20. #define STLR(i,con) for(int i=0,sz=con.size();i<sz;++i)
  21. #define STLRD(i,con) for(int i=con.size()-1;0<=i;--i)
  22. #define CLR(s) memset(s,0,sizeof s)
  23. #define SET(s,v) memset(s,v,sizeof s)
  24. #define mp make_pair
  25. #define pb push_back
  26. #define x first
  27. #define y second
  28. using namespace std;
  29. typedef long long LL;
  30. typedef double DB;
  31. const int INF = 0x3f3f3f3f;
  32.  
  33. struct Data
  34. {
  35.     vector<int> str;
  36.     void clear()
  37.     {
  38.         str.clear();
  39.     }
  40.     int size()
  41.     {
  42.         return str.size();
  43.     }
  44.     void push_back(int t)
  45.     {
  46.         str.push_back(t);
  47.     }
  48.     void print()
  49.     {
  50.         STLR(i,str)
  51.             printf("%c",char(str[i]));
  52.         puts("");
  53.     }
  54.     int &operator [] (int i)
  55.     {
  56.         return str[i];
  57.     }
  58. };
  59. vector<Data> S;
  60. Data tmp;
  61.  
  62. int n;
  63. bool check(int t)
  64. {
  65.     return t==(int)'*';
  66. }
  67.  
  68. vector<int> next;
  69.  
  70. void get_next(int l,int r,int s)
  71. {
  72.     next.clear();
  73.     next.pb(-1);
  74.     int i=l,j=-1;
  75.     while(i<=r)
  76.     {
  77.         if(j==-1 || S[s][i]==S[s][j+l])
  78.         {
  79.             ++i,next.pb(++j);
  80.         }
  81.         else
  82.             j=next[j];
  83.     }
  84. }
  85.  
  86. bool kmp(int s,int l,int r,int p,int &i)
  87. {
  88.     get_next(l,r,s);
  89.  
  90.     int j=l-1;
  91.     --i;
  92.     int len=S[p].size();
  93.     while(i<len)
  94.     {
  95.         if(j==l-1 || S[s][j]==S[p][i])
  96.         {
  97.             ++i,++j;
  98.             if(j==r+1)
  99.             {
  100.                 --i;
  101.                 return true;
  102.             }
  103.         }
  104.         else
  105.             j=next[j-l]+l;
  106.     }
  107.     return false;
  108. }
  109.  
  110. vector<int> stop;
  111. vector<pair<int,int> > block;
  112. bool same_with_kmp(int s,int p)
  113. {
  114.     stop.clear();
  115.     block.clear();
  116.     stop.pb(-1);
  117.     STLR(i,S[s])
  118.     {
  119.         if(check(S[s][i]))
  120.             stop.pb(i);
  121.     }
  122.     stop.pb(S[s].size());
  123.     int a,b;
  124.     for(int i=1,sz=stop.size();i<sz;++i)
  125.     {
  126.         a=stop[i-1]+1,b=stop[i]-1;
  127.         if(b<a) continue;
  128.         block.pb(mp(a,b));
  129.     }
  130.  
  131.     int run=0;
  132.     STLR(i,block)
  133.     {
  134.         if(!kmp(s,block[i].x,block[i].y,p,run))
  135.             return false;
  136.     }
  137.  
  138.     return true;
  139. }
  140.  
  141. bool check_with_kmp()
  142. {
  143.     int a=-1,mark=INF;
  144.     bool flag;
  145.     STLR(i,S)
  146.     {
  147.         flag=false;
  148.         STLR(j,S[i])
  149.         {
  150.             if(check(S[i][j]))
  151.             {
  152.                 flag=true;
  153.                 break;
  154.             }
  155.         }
  156. //      printf("%d %d %d\n",flag,S[i].size(),mark);
  157.         if(!flag && S[i].size()<mark)
  158.         {
  159.             mark=S[i].size();
  160.             a=i;
  161.         }
  162.     }
  163.  
  164.  
  165.     if(a==-1)
  166.         return true;
  167.  
  168.     STLR(i,S)
  169.     {
  170.         if(!same_with_kmp(i,a))
  171.             return false;
  172.     }
  173.  
  174.     return true;
  175. }
  176.  
  177.  
  178. bool same_with_tp(int s,int a,int b)
  179. {
  180.     STLR(i,S[s])
  181.     {
  182.         if(check(S[a][i]) || check(S[s][i]))
  183.             break;
  184.         if(S[a][i]!=S[s][i])
  185.             return false;
  186.     }
  187.     STLR(i,S[s])
  188.     {
  189.         if(check(S[s][S[s].size()-i-1]) || check(S[b][S[b].size()-i-1]))
  190.             break;
  191.         if(S[s][S[s].size()-i-1]!=S[b][S[b].size()-i-1])
  192.             return false;
  193.     }
  194.     return true;
  195. }
  196.  
  197. bool check_with_tp()
  198. {
  199.     int a=0,b=0;
  200.     int mark1=-1,mark2=-1;
  201.     STLR(i,S)
  202.     {
  203.         STLR(j,S[i])
  204.         {
  205.             if(check(S[i][j]))
  206.             {
  207.                 if(j>mark1)
  208.                 {
  209.                     mark1=j;
  210.                     a=i;
  211.                 }
  212.                 break;
  213.             }
  214.         }
  215.         STLRD(j,S[i])
  216.         {
  217.             if(check(S[i][j]))
  218.             {
  219.                 if(S[i].size()-j>mark2)
  220.                 {
  221.                     mark2=S[i].size()-j;
  222.                     b=i;
  223.                 }
  224.                 break;
  225.             }
  226.         }
  227.     }
  228.  
  229.     //printf("%d %d\n",a,b);
  230.  
  231.     STLR(i,S)
  232.     {
  233.         if(!same_with_tp(i,a,b))
  234.             return false;
  235.     }
  236.  
  237.     return true;
  238. }
  239.  
  240. char s[20000000];
  241. int main()
  242. {
  243.  
  244.     int T;
  245.     scanf("%d",&T);
  246.     while(T--)
  247.     {
  248.         scanf("%d",&n);
  249.         S.clear();
  250.         for(int i=0;i<n;++i)
  251.         {
  252.             scanf("%s",s);
  253.         //  printf("%s\n",s);
  254.             tmp.clear();
  255.             for(int j=0;s[j]!='\0';++j)
  256.                 tmp.pb((int)s[j]);
  257.             S.pb(tmp);
  258.         }
  259.         bool flag1=check_with_tp();
  260.         bool flag2=check_with_kmp();
  261.         if(flag1 && flag2) puts("Y");
  262.         else puts("N");
  263.     }
  264.     fclose(stdin);
  265.     fclose(stdout);
  266.  
  267.     return 0;
  268. }
Success #stdin #stdout 0s 22960KB
comments (?)
stdin
copy 
3              

3               

wellplayed      

thankyou       

pyroblast       

2               

a*abc           

abc*a         

2               

a*abc           

a1234567890abc
stdout
copy 
N
N
Y
https://ideone.com/HsFBm4
HNOI2014 抄卡组 hs
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!