Advertisement
Malinovsky239

Untitled

Feb 6th, 2012
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <map>
  6.  
  7. #define L int(3e5)
  8.  
  9. using namespace std;
  10.  
  11. int res = 0, mem = 1, l[L], beg[L];
  12. char s[L];
  13.  
  14. map< pair<int, int>, bool > record;
  15.  
  16. int main() {
  17.     freopen("chain.in", "r", stdin);
  18.     freopen("chain.out", "w", stdout);
  19.  
  20.     int m, k, prev, pos = 0, start = 0;
  21.     scanf("%d ", &m);
  22.     for (int i = 0; i < m; i++) {
  23.         gets(s + pos);
  24.         beg[i] = pos;
  25.         l[i] = strlen(s + pos);    
  26.         pos += l[i];               
  27.     }
  28.  
  29.     scanf("%d ", &k);
  30.     scanf("%d", &prev);
  31.     prev--;
  32.     for (int i = 1; i < k; i++) {
  33.         int now;
  34.         scanf("%d ", &now);
  35.         now--;     
  36.  
  37.         if (l[now] <= l[prev]) {
  38.             start = i, prev = now;
  39.             continue;
  40.         }
  41.  
  42.         if (record.count(make_pair(prev, now))) {
  43.             if (record[make_pair(prev, now)]) {
  44.                 if (i - start > res) {
  45.                     res = i - start;
  46.                     mem = start;               
  47.                 }                                                                  
  48.             }
  49.             else {
  50.                 start = now;               
  51.             }
  52.             prev = now;
  53.             continue;      
  54.         }
  55.  
  56.         bool ok = true;
  57.         for (int j = 0; j < l[prev]; j++) {    
  58.             if (s[ beg[now] + j] != s[ beg[prev] + j]) {
  59.                 ok = false;
  60.                 break;             
  61.             }          
  62.         }
  63.  
  64.         if (ok) {
  65.             record[ make_pair(prev, now) ] = true;
  66.             if (i - start > res) {
  67.                 res = i - start;
  68.                 mem = start;               
  69.             }                      
  70.         }
  71.         else {
  72.             record[ make_pair(prev, now) ] = false;
  73.             start = i;
  74.         }
  75.  
  76.         prev = now;
  77.     }
  78.  
  79.     printf("%d %d\n", mem + 1, mem + res + 1);
  80.  
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement