Advertisement
ahmed_aly

Untitled

Apr 30th, 2011
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. int main() {
  2.     cin >> str >> n;
  3.     rep(i,n)
  4.         cin >> strs[i];
  5.     len = sz(str);
  6.     int ind = n;
  7.     for (int i = len - 1; i >= 0; i--) {
  8.         string temp = str.substr(i, 1);
  9.         if (dp[i + 1])
  10.             temp += str.substr(i + 1, min(9, dp[i + 1]));
  11.         int mn = oo;
  12.         rep(j,n) {
  13.             int i1 = 0, i2 = 0;
  14.             while (i1 < sz(temp) && i2 < sz(strs[j])) {
  15.                 if (temp[i1] != strs[j][i2])
  16.                     break;
  17.                 i1++;
  18.                 i2++;
  19.             }
  20.             if (i2 == sz(strs[j]))
  21.                 mn = min(mn, sz(strs[j]));
  22.         }
  23.         if (mn == oo)
  24.             dp[i] = dp[i + 1] + 1;
  25.         else
  26.             dp[i] = mn - 1;
  27.         if (dp[i] >= dp[ind])
  28.             ind = i;
  29.     }
  30.     cout << dp[ind] << " " << ind << endl;
  31.     return 0;
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement