最长前缀 Longest Prefix

最易懂的题解

题目描述

做题时的垂死挣扎

最先看到这道题，非常开心。哈哈一笑，暴力，然后快乐TLE

请大家以我为戒，做题前先看标签。

然后在看到DP后，我傻眼了。（我打的就是dp啊，怎么会错一个点）

我盯着电脑，看着题，想了50多分钟无关的事后。。。我终于开始了打代码

思路

读入时需要注意一下字符串的技巧。

然后你就~~暴力循环~~dp

我最开始TLE一个点是因为，我顺便把连成长度为 K 的前缀的方法总数也顺便求了一下

具体方法

每向后移一个字母，就循环一下元素，看看当前元素是否与这序列从当前位置向前遍

历所的串相等

for(k = i;k > i - a[j].k[11];k--)
{
    it--;
    if(a2[k] != a[j].k[it])
	{
        able = 1;
    	break;
    }
}

且

dp[k - 元素.size()] == 1

才将


dp[k] = 1;

最后再在一些地方适当优化就可以AC了

我的方法

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 200002
#define N 202
#define max(a,b) a >= b? a:b//手写max
using namespace std;
int ans,len1,i,j,len2 = 1;
char a2[M];
bool dp[M];
struct node
{
	char k[12];
}a[N];//主要是定义成结构体，看着好看一些，可以定成二维

int main()
{
    scanf("%s",a[len2].k);
    a[len2].k[11] = strlen(a[len2].k);//最大长度10,11存长度
    while(a[len2].k[0] != '.')//不能写成a[len2].k !=  "."
	{
        len2++;
        scanf("%s",a[len2].k);
        a[len2].k[11] = strlen(a[len2].k);
    }
    len2--;
    char x = getchar();//去掉'.'后的换行符
    
    while(~scanf("%c",&x))
        if(x <= 'Z'&&x >= 'A')
		{
            len1++;
            a2[len1] = x;
        }
    //至此，读入环节结束
    dp[0] = 1;
    for(i = 1;i <= len1;i++)
	{
        int k;
        for(j = 1;j <= len2;j++)
		{
            if(i < a[j].k[11]) continue;//i < 长度，肯定不行的啦
            bool able = 0;
            int it = a[j].k[11];//因为下面--
            for(k = i;k > i - a[j].k[11];k--)
			{
                it--;
                if(a2[k] != a[j].k[it])
				{
                    able = 1;
                    break;
                }
            }
            if(!able)
			{
                dp[i] += dp[i - a[j].k[11]];//就这里，顺便求了下连成长度为 K 的前缀的方法总数
                
                if(dp[i])
                {
                	ans = max(ans,i);
                	break;//必须加，不然会TLE一个点
				}
            }
        }
    }
    printf("%d",ans);
    return 0;
}

总结

时间复杂度能减则减