SRM409 Div2 Medium

500

やるだけ

view plainprint?

1. string f(string a, string b, int &idx)  
2. {  
3.   if (a.size() < b.size()) {  
4.     for (int i = idx; i < (int)a.size(); ++i) {  
5.       string p = a.substr(i);  
6.       string q = b.substr(0, a.size() - i);  
7.       if (p == q) {  
8.         idx = i;  
9.         return a + b.substr(a.size() - i);  
10.       }  
11.     }  
12.   } else {  
13.     for (int i = idx; i < (int)a.size(); ++i) {  
14.       int mn = min(a.size() - i, b.size());  
15.       string p = a.substr(i, mn);  
16.       string q = b.substr(0, mn);  
17.       if (p == q) {  
18.         idx = i;  
19.         return a + b.substr(mn);  
20.       }  
21.     }  
22.   }  
23.   idx = a.size();  
24.   return a + b;  
25. }  
26.   
27. class OrderedSuperString {  
28. public:  
29.   int getLength(vector <string> ws)  
30.   {  
31.     int idx = 0;  
32.     for (int i = 1; i < (int)ws.size(); ++i) {  
33.       ws[i] = f(ws[i - 1], ws[i], idx);  
34.     }  
35.   
36.     return ws.back().size();  
37.   }  
38. };  

string f(string a, string b, int &idx)
{
  if (a.size() < b.size()) {
    for (int i = idx; i < (int)a.size(); ++i) {
      string p = a.substr(i);
      string q = b.substr(0, a.size() - i);
      if (p == q) {
        idx = i;
        return a + b.substr(a.size() - i);
      }
    }
  } else {
    for (int i = idx; i < (int)a.size(); ++i) {
      int mn = min(a.size() - i, b.size());
      string p = a.substr(i, mn);
      string q = b.substr(0, mn);
      if (p == q) {
        idx = i;
        return a + b.substr(mn);
      }
    }
  }
  idx = a.size();
  return a + b;
}

class OrderedSuperString {
public:
  int getLength(vector <string> ws)
  {
    int idx = 0;
    for (int i = 1; i < (int)ws.size(); ++i) {
      ws[i] = f(ws[i - 1], ws[i], idx);
    }

    return ws.back().size();
  }
};