Source code for submission s1401

bugs.cpp

  1. //
  2. // File:   bugs.cc
  3. // Author: cteam051
  4. //
  5. // Created on October 27, 2012, 1:55 PM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <cstdio>
  10. #include <cstring>
  11.  
  12.  
  13. char Bug [1001];
  14. char line [2000001];
  15. char res[2000001];
  16. int resLen;
  17. int nexts[2000001];
  18.  
  19. void rec(int i){
  20.     int result=0;
  21.     int bugI=1;
  22.     int startI=i;
  23.     i=nexts[i];
  24.     while(bugI<strlen(Bug)){
  25.         if (Bug[0]==line[i-1]){
  26.             rec(nexts[i]);            
  27.         }
  28.         if (Bug[bugI]!=line[i-1]){            
  29.             return;
  30.         }
  31.         i=nexts[i];
  32.         bugI++;
  33.     }
  34.     nexts[startI-2]=i;
  35.     return;
  36. }
  37.  
  38.  
  39. void first(){
  40.     int i;
  41.     resLen=0;
  42.     int lineLen=strlen(line);
  43.     for (int k=0; k<lineLen; k++){
  44.         nexts[k]=k+1;
  45.     }
  46.     i=1;
  47.     while (i-1!=lineLen){
  48.         if (line[i-1]==Bug[0])
  49.             rec(nexts[i]);        
  50.         i=nexts[i];
  51.  
  52.     }
  53.     i=0;
  54.     while (i-1!=lineLen){
  55.         i=nexts[i];
  56.         res[resLen++]=line[i-1];
  57.     }
  58.     res[resLen]='\0';
  59.     printf("%s\n", res);
  60.  
  61. }
  62.  
  63. int main(int argc, char** argv) {
  64.  
  65.     int N;
  66.     while (true) {
  67.         if (scanf("%d ", &N)!=1)return (0);
  68.         gets(Bug);
  69.         for (int idx = 0; idx < N; idx++) {
  70.             gets(line);
  71.             first();
  72.         }
  73.  
  74.     }
  75.  
  76.     return (0);
  77. }
  78.  
  79.  
  80.  
  81.