hiho week 227 register

Ended

Participants:116

Verdict:Accepted
Score:100 / 100
Submitted:2018-11-04 21:16:34

Lang:G++

Edit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5, S = 1e5+5;
char s[100005], wp[S+N], * w[S];
int main() {
    int n;
    scanf("%d", &n);
    w[0] = wp;
    for (int i = 1; i<=n; ++i) {
        w[i] = w[i-1] + strlen(w[i-1]) + 1;
        scanf("%s", w[i]);
    }
    scanf("%s", s+1);
    set<int> pos[300];
    int m = strlen(s+1);
    for (int i = 1; i<=m; ++i) pos[s[i]].insert(i);
    int ans = 0;
    for (int i = 1; i<=n; ++i) {
        int x = m;
        for (int j = strlen(w[i]); j-- && x>=0;)
            if (pos[w[i][j]].upper_bound(x)!=pos[w[i][j]].begin())
                x = *--pos[w[i][j]].upper_bound(x) - 1;
            else
                x = -1;
        if (x>=0) ans = max(ans, (int)strlen(w[i]));
//      printf("strlen(w[%d]) = %d\n", i, (int)strlen(w[i]));
    }
    printf("%d\n", ans);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX