1215:Co-occurrence Search

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1215

文字列といくつかの文字が与えられる。
文字をすべて含む、文字列の部分列の中で最小の長さのものの個数と、そのような部分列のなかで最初に現れるものを出力せよ。

尺取り法のようなことをした。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

#define INF (1<<29)
#define all(c) (c).begin(),(c).end()

using namespace std;


int main(void){

  string s,t,in;
  while(true){
    s.clear();
    t.clear();
    while(true){
      getline(cin,in);
      if(in.size()==0)break;
      s+=in;
    }

    while(true){
      getline(cin,in);
      if(in.size()==0)break;
      t+=in;
    }

    if(s.size()==0 && t.size()==0)break;

    int sl=s.size(),tl=t.size();
    int now[tl],ans=0;
    string res="";

    fill(now,now+tl,INF);

    int tmp=0;
    for(int i=0;i<sl;i++){
      for(int j=0;j<tl;j++){
        if(s[i]==t[j]){
          now[j]=min(now[j],i);
        }
      }
    }

    bool flag=false;
    for(int i=0;i<tl;i++){
      flag|=(now[i]>=INF);
    }
    if(flag){
      cout << 0 << endl << endl;;
      continue;
    }

    int left=INF,right=-1,lid,rid;
    for(int i=0;i<tl;i++){
      if(left>now[i])left=now[i],lid=i;
      if(right<now[i])right=now[i],rid=i;
    }
    ans++;
    res=s.substr(left,right-left+1);

    while(true){
      int mn=INF,id=0;
      for(int i=0;i<tl;i++){
        if(mn>now[i])mn=now[i],id=i;
      }
      while(now[id]<sl && s[++now[id]]!=t[id]);
      if(s[now[id]]!=t[id])break;
      int l=INF,r=0;
      bool fg=true;
      for(int i=0;i<tl;i++){
        l=min(l,now[i]);
        r=max(r,now[i]);
        fg&=(now[i]>=sl-1);
      }
      if(fg)break;
      if(res.size()>r-l+1){
        ans=0;
        res=s.substr(l,r-l+1);
      }
      if(res.size()==r-l+1)ans++;
    }
    cout << ans << endl << endl;
    for(int i=0;i<res.size();i++){
      cout << res[i];
      if((i+1)%72==0)cout << endl;
    }
    if(res.size()%72>0)cout << endl;
    cout << endl;
  }
  return 0;
}