naoya_t@topcoder

SRM392 Div1 Easy: TwoStringMasks

過去問, 練習 | 08:46 |

文字列操作。split()は自前。

class TwoStringMasks {
public:
  string shortestCommon(string s1, string s2) {
    vector<string> v1 = split(s1,'*'), v2 = split(s2,'*');
    int l1a=v1[0].length(), l1b=v1[1].length(),
      l2a=v2[0].length(), l2b=v2[1].length();
    int coma=min(l1a,l2a), comb=min(l1b,l2b);
    if(coma>0){
      if (v1[0].substr(0,coma)!=v2[0].substr(0,coma)) return "impossible";
    }
    if(comb>0){
      if (v1[1].substr(l1b-comb,comb)!=v2[1].substr(l2b-comb,comb)) return "impossible";
    }
    string prefix = v1[0].substr(0,coma), suffix = v1[1].substr(l1b-comb,comb);
    v1[0]=(l1a==coma)?"":v1[0].substr(coma,l1a-coma); l1a-=coma;
    v2[0]=(l2a==coma)?"":v2[0].substr(coma,l2a-coma); l2a-=coma;
    v1[1]=(l1b==comb)?"":v1[1].substr(0,l1b-comb); l1b-=comb; // l1b==comaとか書いてて結果が合わなかったりした。substrは長さに0を渡しても大丈夫なのでこのチェックは不要だった
    v2[1]=(l2b==comb)?"":v2[1].substr(0,l2b-comb); l2b-=comb;
    string a=(l1a>l2a)?v1[0]:v2[0], b=(l1b>l2b)?v1[1]:v2[1];
    if ((l1a>=l2a && l1b>=l2b) || (l1a<l2a && l1b<l2b)) return prefix + a + b + suffix;

    int al=a.length(), bl=b.length();
    for(int l=min(al,bl);l>0;l--) {
      if (a.substr(al-l,l)==b.substr(0,l))
        return prefix + a + b.substr(l,bl-l) + suffix;
    }
    return prefix + a + b + suffix;
  }
};

string.substr()の

• 長さは0でもよい
• 長さのデフォルトはstd::npos（末尾まで）なので、文字列途中から末尾までのsubstringを取りたい場合は第２引数を省略すればいい

という性質を理解していれば煩雑さが少しばかり減る：

class TwoStringMasks {
public:
  string shortestCommon(string s1, string s2) {
    vector<string> v1 = split(s1,'*'), v2 = split(s2,'*');
    int l1a=v1[0].length(), l1b=v1[1].length(),
      l2a=v2[0].length(), l2b=v2[1].length();
    int coma=min(l1a,l2a), comb=min(l1b,l2b);
    if(coma>0){
      if (v1[0].substr(0,coma)!=v2[0].substr(0,coma)) return "impossible";
    }
    if(comb>0){
      if (v1[1].substr(l1b-comb)!=v2[1].substr(l2b-comb)) return "impossible";
    }

    string prefix = v1[0].substr(0,coma), suffix = v1[1].substr(l1b-comb);
    v1[0]=v1[0].substr(coma); l1a-=coma;
    v2[0]=v2[0].substr(coma); l2a-=coma;
    v1[1]=v1[1].substr(0,l1b-comb); l1b-=comb;
    v2[1]=v2[1].substr(0,l2b-comb); l2b-=comb;
    string a=(l1a>l2a)?v1[0]:v2[0], b=(l1b>l2b)?v1[1]:v2[1];
    if ((l1a>=l2a && l1b>=l2b) || (l1a<l2a && l1b<l2b)) return prefix + a + b + suffix;

    int al=a.length(), bl=b.length();
    for(int l=min(al,bl);l>0;l--) {
      if (a.substr(al-l)==b.substr(0,l))
        return prefix + a + b.substr(l) + suffix;
    }
    return prefix + a + b + suffix;
  }
};