c - 给定数组是另一个数组的子序列

Question

构建一个代码来检查 s_array[] 中的一组数字是否是 array[] 的子序列，这意味着 { 1 , 5, 4 } 不是 array 的子序列，而 { 1, 4, 5} 是一个(顺序很重要)

我的代码将首先检查 s_array[] 的第一个元素是否存在于 array[] 中，一旦找到公共(public)元素，它将继续检查其余元素是否存在s_array[] 的元素也存在于 array[] 中并且顺序相同(其他元素可以在它们之间)

#include <stdio.h>
void main(){
    int s_array[] = { 5, 7, 13 };
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
    int i, Bcount, m, counter = 1, j = 4;
    //i, Bcount and m are loop counters
    //counter will count number of repeated elements
    //j is the number of elements in s_array + 1

    for( i = 0; i <= 15; i++ ){
        if( s_array[0] == array[i] ){ // does the first element exist?
            for( Bcount = 1; Bcount < j; Bcount++ ){ //checking the rest 
                for( m = i; m < 15; m++){
                    if( s_array[Bcount] == array[m] ){
                        counter++;
                        i = m;
                        break;
                    }
                }

            }
        }
        if( j == counter ){
               printf( "B is a sub-sequence of A.\n" );
               break;
        }
        else{
               printf( "B is not a sub-sequence of A.\n" );
               break;
        }
    }
}

老实说，我看不出是算法问题还是我在编码方面做错了什么

Answer 1

首先，第一个循环是错误的，因为 i 上升到 15 并且在这个索引处您访问 array 越界(未定义行为)。

那么循环就很简单了。你只需要

• 一个循环 i 数组索引和 si s_array
• 只有在 s_array[si] 中找到数字 array[i] 时才递增 si
• 如果 i 覆盖了数组，则停止循环，或如果 si 得到子数组元素的数量 ( 3)
• 如果si至少为3，则子序列被找到

也就是

int s_array[] = { 5, 7, 13 };
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

 int si,i;
 for (si=0,i=0 ; i<15 && si<3 ; i++) {
    if (s_array[si] == array[i]) si++;
 }

 printf ("Sub was %s\n", si<3 ? "not found":"found");