HDU 1841： Find the Shortest Common Superstring

客官°小女子只卖身不卖艺 2022-08-03 03:20 9阅读 0赞

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char a[2000005],b[2000005];
    int nextd[2000010];
    void get(char *ch)
    {
    	int l = strlen(ch);
    	int s = 0,t = -1;
    	nextd[0] = -1;
    	while(s <l)
    	{
     		if(t == -1|| ch[s] == ch[t])
     		{
     			t++;
     			nextd[++s] = t;
     		}
     		else
     		t = nextd[t];
    	}
    }
    int  kmpd(char *ch1,char *ch2)
    {
    	get(ch2);
    	int l1 = strlen(ch1);
    	int l2 = strlen(ch2);
    	int s = 0,t = 0;
    	int ma=0;
    	while(s <l1&&t<l2)
    	{
     		if(t == -1 || ch1[s] == ch2[t])
     		{
     			t++;
     			s++;
     		
     		}
     		else
     		t = nextd[t];
    	}
    	return t;
    }
    int main()
    {
    	int i,j,k,n,m,l;
    	while(~scanf("%d",&n))
    	{
    		while(n--)
    		{
    		scanf("%s %s",a, b);
    		int la = strlen(a);
    		int lb = strlen(b);
    		int l1 = kmpd(a, b);
    		int l2 = kmpd(b, a);
    		//printf("%d %d\n",l1,l2);
    		printf("%d\n",la + lb - max(l1,l2));
    		}
    	
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1841 Find the Shortest Common Superstring（KMP）

Find the Shortest Common Superstring Problem Description The shortest common su

淡淡的烟草味﹌/ 2024年02月17日 21:13/ 0 赞/ 45 阅读

相关 cisco1841(cisco1841路由器设置步骤)

Cisco1841路由器路由器，以太口，不能配成与其它接口同一网段或有互相包含关系(以太-以太，以太-串行都不行)。串口之间可以，甚至同一地址都允许。路由器，毕竟

喜欢ヅ旅行/ 2023年09月26日 13:42/ 0 赞/ 178 阅读

相关【树状数组】【2019hdu多校】Find the answer

题意：每次从1到i-1中选择最少的数减为0，确保1到i的前缀和小于m，我们离散化，从小到大排序，按照输入顺序每遍历一个就插入到树状数组在排序过后的位置，二分位置确保树状数组的前

客官°小女子只卖身不卖艺/ 2023年06月01日 08:46/ 0 赞/ 15 阅读

相关杭电-1595find the longest of the shortest（记录路径最短路径中最长路）

find the longest of the shortest Time Limit: 1000/5000 MS (Java/Others) Memory Limit:

女爷i/ 2022年08月17日 15:12/ 0 赞/ 147 阅读

相关 HDU 1841： Find the Shortest Common Superstring

include<stdio.h> include<string.h> include<algorithm> using namespace st

客官°小女子只卖身不卖艺/ 2022年08月03日 03:20/ 0 赞/ 10 阅读

相关 hdu----Find Q

Byteasar is addicted to the English letter 'q'. Now he comes across a string S![Image 1

谁借莪１个温暖的怀抱￠/ 2022年06月15日 01:37/ 0 赞/ 163 阅读

相关 hdu 1159 Common Subsequence

Problem Description A subsequence of a given sequence is the given sequence with some e

喜欢ヅ旅行/ 2022年05月31日 02:10/ 0 赞/ 125 阅读

相关 HDU-1595-find the longest of the shortest

find the longest of the shortest Time Limit: 1000/5000 MS (Java/Others) Memory Lim

太过爱你忘了你带给我的痛/ 2022年05月20日 10:41/ 0 赞/ 154 阅读

相关 hdu-1596-find the safest road

find the safest road Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/3

拼搏现实的明天。/ 2022年05月20日 08:38/ 0 赞/ 144 阅读

相关 HDU 1594 find the max

数序问题。题意是说一个数列 a1,a2,……ai,……an; x=i , y = ai；找两个点斜率绝对值。！最大。第一次没找绝对值，……认真读题。。

Love The Way You Lie/ 2021年11月16日 06:28/ 0 赞/ 357 阅读