C语言：数据子序列基础版

Question

描述
有两个数据集合A和B升序有序排列 是设计一种算法 判断B是不是A的子序列 是则数组B在A的起止位置。如A={1 3 5 6 7 8 11} B={5 6 7 8} 则B是A的子序列。其位置是3 6 否则输出0 0。
输入
输入数据有多行 第一行是一个正整数N 表示有N组测试数据 随后的2N行是N组测试数据A和B数据序列 如样例所示。
输出
B是A的子序列 则输出B在A的起止位置 空格隔开 否则输出0 0。
难度
较难
输入示例
2
1 3 5 6 7 8 11
5 6 7 8
11 15 16 27 58 11100
11 27 58

输出示例
3 6
0 0

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

#include <stdio.h>
#include <stdlib.h>
 
// 二分查找函数，查找数组arr中是否存在目标元素target，若存在则返回其下标，否则返回-1
int binarySearch(int *arr, int low, int high, int target)
{
    int mid;
    
    while(low <= high)
    {
        mid = (low + high) / 2;
        if(target < arr[mid])
            high = mid - 1;
        else if(target > arr[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}
 
int main()
{
    int n, target, left, capacity = 2048, lenA, lenB;
    int *array = (int*)calloc(capacity, sizeof(int)); // 动态分配数组，初始容量为2048
    char c;
    
    scanf("%d", &n); // 读取n的值
    int results[n][2]; // 存储结果的二维数组，每个结果占2个元素
 
    int i;
    for(i = 0; i < n; i++)
    {
        lenA = lenB = 0; // 初始化lenA和lenB为0，分别表示数组A和数组B的长度
        for(; scanf("%d%c", &target, &c) == 2;) // 读取数组A的元素，直到遇到换行符
        {
            if(lenA >= capacity) // 如果数组A长度已经达到当前容量，则扩充容量为原来的2倍
            {
                capacity *= 2;
                array = (int*)realloc(array, capacity * sizeof(int));
            }
            array[lenA++] = target; // 将读取到的元素放入数组A中
            if(c == '\n') // 如果遇到换行符，则表示数组A的元素读取完毕
                break;
        }
        for(; scanf("%d%c", &target, &c) == 2;) // 读取数组B的元素，直到遇到换行符
        {
            if(lenB >= capacity) // 如果数组B长度已经达到当前容量，则扩充容量为原来的2倍
            {
                capacity *= 2;
                array = (int*)realloc(array, capacity * sizeof(int));
            }
            array[lenA + lenB++] = target; // 将读取到的元素放入数组B中
            if(c == '\n') // 如果遇到换行符，则表示数组B的元素读取完毕
                break;
        }
        c = 0; // 用于记录是否找到匹配的子数组
        left = binarySearch(array, 0, lenA - 1, array[lenA]); // 在数组A中查找第二个元素的位置
        for(; left >= 0 && array[left] == array[lenA]; left--) // 向左遍历，直到不等于第二个元素
            ;
        for(left++; left <= lenA && array[left] == array[lenA]; left++) // 从第一个元素位置向右遍历
        {
            int matched = 1; // 判断是否找到匹配的子数组
            for(target = 0; target < lenB; target++) // 遍历数组B中的元素
            {
                if(array[left + target] != array[lenA + target]) // 如果元素不匹配
                {
                    matched = 0; // 匹配为0
                    break;
                }
            }
            if(matched) // 如果找到匹配的子数组
            {
                results[i][0] = left + 1; // 记录子数组起始位置
                results[i][1] = left + lenB; // 记录子数组结束位置
                c = 1; // 设置标志变量c为1
                break;
            }    
        }
        if(c == 0) // 如果未找到匹配的子数组
        {
            results[i][0] = 0; // 子数组起始位置为0
            results[i][1] = 0; // 子数组结束位置为0
        }
        
        lenA += lenB; // 更新数组A的长度
    }
 
    int k;
    for(k = 0; k < n; k++) // 输出结果
    {
        printf("%d %d\n", results[k][0], results[k][1]);
    }
    
    free(array); // 释放动态分配的数组空间
    return 0;
}