Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- #include <map>
- #define L int(3e5)
- using namespace std;
- int res = 0, mem = 1, l[L], beg[L];
- char s[L];
- map< pair<int, int>, bool > record;
- int main() {
- freopen("chain.in", "r", stdin);
- freopen("chain.out", "w", stdout);
- int m, k, prev, pos = 0, start = 0;
- scanf("%d ", &m);
- for (int i = 0; i < m; i++) {
- gets(s + pos);
- beg[i] = pos;
- l[i] = strlen(s + pos);
- pos += l[i];
- }
- scanf("%d ", &k);
- scanf("%d", &prev);
- prev--;
- for (int i = 1; i < k; i++) {
- int now;
- scanf("%d ", &now);
- now--;
- if (l[now] <= l[prev]) {
- start = i, prev = now;
- continue;
- }
- if (record.count(make_pair(prev, now))) {
- if (record[make_pair(prev, now)]) {
- if (i - start > res) {
- res = i - start;
- mem = start;
- }
- }
- else {
- start = now;
- }
- prev = now;
- continue;
- }
- bool ok = true;
- for (int j = 0; j < l[prev]; j++) {
- if (s[ beg[now] + j] != s[ beg[prev] + j]) {
- ok = false;
- break;
- }
- }
- if (ok) {
- record[ make_pair(prev, now) ] = true;
- if (i - start > res) {
- res = i - start;
- mem = start;
- }
- }
- else {
- record[ make_pair(prev, now) ] = false;
- start = i;
- }
- prev = now;
- }
- printf("%d %d\n", mem + 1, mem + res + 1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement