最长前缀问题，时间超限和部分答案错误，求大佬帮忙看看

Question

一、最长前缀问题描述

二、我的代码

#include<stdio.h>
#include<string.h>


void Len_Max(char (*ga)[10], char *seq, int ga_pos, int seq_pos, int *res);
int Match(char *ga, char *seq);

int main()
{
    char ga[200][10] = {'\0'};
    char seq[200000] ={'\0'};
    int i;
    int res = 0;

    for(i = 0; i < 200; i++)
    {
        scanf("%s", ga[i]);
        if (strcmp(ga[i], ".") == 0)
            break;
    }
    getchar();  //吃掉回车
    i = 0;
    while(scanf("%c", &seq[i]) != EOF)
    {
        if (seq[i] != '\n') //忽略回车
            i++;
        if (i >= 200000)
            break;
    }
    Len_Max(ga, seq, 0, 0, &res);
    printf("%d\n", res);

    return 0; 
}
//迭代求出所有前缀长度的情况，取最长返回
void Len_Max(char (*ga)[10], char *seq, int ga_pos, int seq_pos, int *res)
{
    int i;
    //让最开始匹配能够匹配集合ga多次
    if (ga_pos == 0 && seq_pos == 0)
    {
        for(i = 1; i < 200; i++)
        {
            if (strcmp(ga[i], ".") == 0)
                break;
            Len_Max(ga, seq, i, seq_pos, res);
        }
    }
    //匹配一个元素，即可进行下一元素的匹配
    if (Match(ga[ga_pos], &seq[seq_pos]) == 1)
    {
        seq_pos += strlen(ga[ga_pos]);
        for(i = 0; i < 200; i++)
        {
            if (strcmp(ga[i], ".") == 0)
                break;
            Len_Max(ga, seq, i, seq_pos, res);
        }
    }
    else
    {
        //匹配不成功，则统计前缀长度，最长的留下
        if(seq_pos > *res)
            *res = seq_pos;
    }
}
//匹配字符串
int Match(char *g, char *seq)
{
    int i;
    for(i = 0; i < 10; i++)
    {
        if(seq[i] != g[i])
            break;
    }
    if(g[i] == '\0')
        return 1;
    else
        return 0;
}

三、报错信息

在test5样例预料的答案1800中，我所输出的与答案不同，我不知道哪里有问题...
在test4样例中，我的答案对是对了，但所用时间花了2s，题目希望要在1s内解决，不知道还能怎样优化代码？

Answer 1

感觉应该是动态规划的题目，然后解题思路应该是这样的
str[i] == 1 表示 前缀0~i能得到，==0则不能得到
然后现在假设某一元素ele[j]，长度为ele[j].length，
判断下这一元素能不能匹配str[i]的后缀，如果不能，赋值0，如果能，在看下位置str[i-ele[j].length]的值是1还是0
0的话表示前缀str[i-ele[j].length]不能得到，赋值0，反之则在之前就已经得到了，赋值1
然后对每一个str[i]的前缀，所有的元素ele都判断一遍，只要能得到一个匹配成功且str[i-ele[j].length]的值为1，就可以赋值为1了
然后i的话从0开始遍历整个序列就行，
应该是背包问题里的完全背包的变种
然后这样下来最坏复杂度会达到200000*200*10，数据量大的话还是会超时
这里可以实现将原先的200个元素构建一棵后缀树，之后用这棵后缀树进行后缀的匹配，可以将复杂度减下来，达到200000*10，应该就行了