fork download
copy 
  1.     #include<cstring>
  2.     #include<cstdio>
  3.     #include<vector> 
  4.     using namespace std;
  5.  
  6.  
  7.     int *overlap;
  8.     char *pattern;
  9.  
  10.    void calcoverlap()
  11.    {
  12.     overlap[0] = 0;
  13.     unsigned int length,i,len;  
  14.     length=strlen(pattern);
  15.  
  16.     while(i<length)
  17.     {
  18.         if (pattern[i] == pattern[len])
  19.         {
  20.             len++;
  21.             overlap[i] = len;
  22.             i++;
  23.         }
  24.         else
  25.         {
  26.             if (len != 0)
  27.             {
  28.                 len = overlap[len-1];
  29.             }
  30.             else
  31.             {
  32.                 overlap[i++] = 0;
  33.             }
  34.         }
  35.  
  36.     }
  37.    }
  38.    vector< int > patternmatching(int m)
  39. {
  40. vector< int > V;
  41. int i = 0, j = 0;
  42. char ch;
  43. while(1)
  44. {
  45. ch = getchar();
  46. if(ch == '\n') break;
  47. while(1)
  48. {
  49. if(ch == pattern[j])
  50. {
  51. j++;
  52. if(j == m)
  53. {
  54. V.push_back(i-m+1);
  55. j = overlap[j];
  56. }
  57. break;
  58. }
  59. else if(j == 0) break;
  60. else j = overlap[j];
  61. }
  62. i++;
  63. }
  64. return V;
  65. }
  66.  
  67.  
  68.  
  69.  
  70.    int main()
  71.    {
  72.         int n,i,sz;
  73.         vector<int> V;
  74.         while(scanf("%d",&n)==1)
  75.         {   
  76.             gets(pattern);
  77.             calcoverlap();
  78.             V=patternmatching(n);
  79.             sz = V.size();
  80.            for(i=0; i < sz; i++)
  81.             printf("%d\n",V[i]);
  82.             if(!sz) printf("\n");
  83.             delete[] pattern;
  84.             delete[] overlap;
  85.         }
  86. return 0;
  87.         }
  88.  
  89.  
  90.  
Success #stdin #stdout 0s 2856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iWAfx9
language:
C++ (gcc 8.3)
created:
12 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!