程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 2954 Simpsons’ Hidden Talents(KMP)

hdu 2954 Simpsons’ Hidden Talents(KMP)

編輯:C++入門知識

題目鏈接:hdu 2954 Simpsons’ Hidden Talents


題目大意:給出兩個字符串,找出一個子串,為s1的前綴,s2的後綴, 要求子串最長,並且輸出該子串。


解題思路:將s1和s2首尾相連,然後求出next數組的next[n+m]的位置,然後和n、m取最小值即為答案。


#include 
#include 
#define min(a,b) (a)<(b)?(a):(b)

const int N = 1e5+5;

int n, m, next[N];
char s1[N], s2[N];

void getNext () {
	int p = 0;
	m = strlen(s1+1);
	for (int i = 2; i <= m; i++) {
		while (p > 0 && s1[p+1] != s1[i])
			p = next[p];

		if (s1[p+1] == s1[i])
			p++;

		next[i] = p;
	}
}

int main () {
	while (scanf("%s%s", s1+1, s2+1) == 2) {
		n = min (strlen(s1+1), strlen(s2+1));
		strcat (s1+1, s2+1);

		getNext ();

		int ans = min (next[m], n);
		for (int i = 1; i <= ans; i++) printf("%c", s1[i]);
		if (ans) printf(" ");
		printf("%d\n", ans);
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved