fork(1) download
  1. #include <bits/stdc++.h>
  2. #include <ext/hash_map>
  3. using namespace std;
  4. using namespace __gnu_cxx;
  5.  
  6. #define oo 1e9
  7. #define ll long long
  8. #define sc(x) scanf("%d",&x)
  9. #define scl(x) scanf("%lld",&x)
  10. #define lop(i,n) for(int i=0;i<n;++i)
  11. #define sz(x) (int)x.size()
  12. #define all(x) x.begin(),x.end()
  13. #define F first
  14. #define S second
  15. #define pi acos(-1)
  16.  
  17. /////// Suffix array //////////////
  18. /// O(NlogN) implementation ////
  19. const int MX=200100,alphabetSize=128;
  20.  
  21. char str[MX];
  22. int n;
  23. int rnk[MX],newRnk[MX],rnkSt[MX],suf[MX],newSuf[MX];
  24. int head[alphabetSize],nxt[MX],lcp[MX];
  25.  
  26. void buildSA(){
  27. memset(head,-1,sizeof head);
  28. for(n=0;!n||str[n-1];++n){
  29. nxt[n]=head[(int)str[n]];
  30. head[(int)str[n]]=n;
  31. }
  32. int ns=0,ng=0; // next start - next group
  33. for(int i=0;i<alphabetSize;i++){
  34. if(head[i]==-1)continue;
  35. rnkSt[ng]=ns;
  36. for(int j=head[i];j!=-1;j=nxt[j]){
  37. suf[ns++]=j;
  38. rnk[j]=ng;
  39. }
  40. ng++;
  41. }
  42. newSuf[0]=suf[0];
  43. ng=0;
  44. for(int len=1;ng!=n-1;len<<=1){
  45. for(int i=0;i<n;i++){
  46. int j=suf[i]-len;
  47. if(j<0)continue;
  48. newSuf[rnkSt[rnk[j]]++]=j;
  49. }
  50. ng=0;
  51. for(int i=1;i<n;i++){
  52. ng+=(rnk[newSuf[i-1]]<rnk[newSuf[i]]
  53. ||(rnk[newSuf[i-1]]==rnk[newSuf[i]]
  54. &&rnk[newSuf[i-1]+len]<rnk[newSuf[i]+len]));
  55. newRnk[i]=ng;
  56. if(newRnk[i]!=newRnk[i-1])rnkSt[ng]=i;
  57. }
  58. for(int i=0;i<n;i++){
  59. suf[i]=newSuf[i];
  60. rnk[suf[i]]=newRnk[i];
  61. }
  62. }
  63. }
  64.  
  65. void buildLCP(){
  66. int cnt=0;
  67. for(int i=0;i<n-1;i++){
  68. int j=suf[rnk[i]-1];
  69. while(str[i+cnt]==str[j+cnt])cnt++;
  70. lcp[rnk[i]]=cnt;
  71. if(cnt)cnt--;
  72. }
  73. }
  74.  
  75. char note[40202];
  76. char str2[MX];
  77. string tmp,tmp2;
  78.  
  79. vector<string> ans;
  80.  
  81. void solve(){
  82. int idx=0;
  83. while(note[idx]){
  84. while(note[idx]&&note[idx]==' ')idx++;
  85. if(!note[idx])break;
  86. int l=0,r=n-1;
  87. int nw=idx;
  88. while(note[nw]>=str[suf[l]+nw-idx]&&note[nw]<=str[suf[r]+nw-idx]){
  89. int l1=l,r1=r,mid;
  90. while(l1<r1){
  91. mid=l1+(r1-l1)/2;
  92. if(str[suf[mid]+nw-idx]>=note[nw])r1=mid;
  93. else l1=mid+1;
  94. }
  95. l=l1;
  96. l1=l,r1=r;
  97. while(l1<r1){
  98. mid=l1+(r1-l1+1)/2;
  99. if(str[suf[mid]+nw-idx]<=note[nw])l1=mid;
  100. else r1=mid-1;
  101. }
  102. r=l1;
  103. if(note[nw]==str[suf[l]+nw-idx]||note[nw]==str[suf[r]+nw-idx])
  104. nw++;
  105. else break;
  106. }
  107. nw--;
  108. tmp="";
  109. int s=suf[l],e=suf[l]+nw-idx;
  110. for(int i=s;i<=e;i++)
  111. tmp+=str2[i];
  112. while(tmp[sz(tmp)-1]==' ')
  113. tmp.erase(tmp.begin()+sz(tmp)-1);
  114. ans.push_back(tmp);
  115. idx=nw+1;
  116. }
  117. }
  118.  
  119. int main() {
  120. #ifndef ONLINE_JUDGE
  121. freopen("input.txt", "rt", stdin);
  122. //freopen("output.txt", "wt", stdout);
  123. #endif
  124. getline(cin,tmp);
  125. for(int i=0;i<sz(tmp);i++)note[i]=tmp[i];
  126. note[sz(tmp)]='\0';
  127. while(getline(cin,tmp))tmp2+=tmp;
  128. for(int i=0;i<sz(tmp2);i++){
  129. str2[i]=tmp2[i];
  130. str[i]=tolower(tmp2[i]);
  131. }
  132. str2[sz(tmp2)]='\0';
  133. str[sz(tmp2)]='\0';
  134. buildSA();
  135. solve();
  136. cout<<sz(ans)<<endl;
  137. for(int i=0;i<sz(ans);i++)
  138. cout<<ans[i]<<endl;
  139. }
  140.  
Success #stdin #stdout 0s 9368KB
stdin
drop the price on new thermopanes now or else
Rain Users Guide
While "rain" was intended to be a general purpose tool, at the time of
writing the primary goal was to study one particular software system.
As a result, some steps that are only done once (such as extracting
information from the program under study) are done using cumbersome
ad-hoc techniques that require significant manual intervention. While
"rain" can be used on arbitrary programs, more development work needs
to be done before this is a convenient process.
stdout
19
d
ro
p
the pri
ce
on
ne
w
the
rm
op
an
es
n
o
w
or
el
se