fork(1) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
19
d
ro
p
the pri
ce
on
ne
w
the
rm
op
an
es
n
o
w
or
el
se
https://ideone.com/7OFcfg
language:
C++14 (gcc 8.3)
created:
8 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!