字符串最大跨距

题意

求字符串 $S$ 中位于左侧且不交叉的 $S1$ 、 $S2$ 的最大跨距。

思路

为了让间隔最大，左边的 $S1$ 应尽量靠左，右边的 $S2$ 应尽量靠右。因此取 find(S1) 和 rfind(S2)；若前者结尾不在后者起点左边，则无合法方案。

代码

Python代码

python

1
2
3
4
5
6
7
8source, first, second = input().split(",")
first_start = source.find(first)
second_start = source.rfind(second)

if first_start == -1 or second_start == -1 or first_start + len(first) > second_start:
    print(-1)
else:
    print(second_start - (first_start + len(first)))

C++代码

cpp

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include <cstdio>
#include <cstring>

char str[500];

char s[5][500];
int idx_1= 1,idx_2=1;
int main(){
    char t;
    while( scanf("%c",&t) != EOF){
        if( t == '\n' || t == '\r')
            break;
        if( t == ','){
            idx_1++;
            idx_2=1;
            continue;
        }
        s[idx_1][idx_2++] = t;
    }

    int point_1_int;
    char * point_1 = strstr(s[1]+1,s[2]+1);
    if( point_1 == NULL){
        printf("-1");
        return 0;
    }
    else 
        point_1_int = point_1 - (s[1]+1);
    //printf("%d\n",point_1_int);
    //reverse
    int len1 = strlen(s[1]+1);
    int len2 = strlen(s[3]+1);
    int i;
    if( strstr(s[1]+1,s[3]+1) == NULL){
        printf("-1");
        return 0;
    }

    for(i = len1;i >= 1;i--){
        char * point_2 = strstr(&s[1][i],s[3]+1);
        if( point_2 != NULL){
            len2 = strlen(s[2]+1);
            //printf("%s\n",s[3]+1);
            //printf("%s\n",point_2);
            //printf("%d\n",point_2-&s[1][1]);
            int ans;
            if( point_2 >= point_1+len2)
                ans = point_2- point_1 -len2;
            else {
                printf("-1");
                return 0;
            }

            printf("%d",ans);
            break;
        }
    }
    return 0;
}

复杂度

字符串查找最坏时间复杂度为 $O(nm)$ ，额外空间复杂度为 $O(1)$ 。

总结

最大间隔由两端极值位置决定，不必枚举全部出现位置。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结