poj 1226 Substrings kmp板题

缘起

日常浪费生命~ poj 1226 Substrings

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
给定n个串，求一个最大子串长度，使得它或者它的逆向串在每个串中出现。

【输入】
多样例.首先是样例数.  每个样例开始于n,1 <= n <= 100,表示字符串的个数.然后是n行, 每行一个字符串, 字符串长度
在[1,100]之间. 

【输出】
对每个样例, 输出最长长度

【样例输入】
2
3
ABCD
BCDFF
BRCD
2
rose
orchid

【样例输出】
2
2 

【限制】
1s

首先注意到本题的数据规模很小, 可以乱搞~

显然, 首先将n个字符串按照长度升序排序(这样可以枚举的少一点), 然后我们只需要从大到小枚举排名第一（即最短的那个字符串）的字符串的子串的长度（可以二分答案, 但是本题数据规模太小了, 没必要）, 然后看看行不行即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
//#include "stdafx.h"
#include <string>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
//#define LOCAL
const int maxn = 105;
string a[maxn];
int n, xnext[maxn],rnext[maxn],m;
char x[maxn], rx[maxn]; //x和x的反串
bool cmp(string &a, string &b)
{
	return a.length()<b.length();
}

void makenext(int len)
{
	xnext[1] = 0;
	for (int i = 2,k;i<=len+1;i++)
	{
		k = xnext[i-1];
		while(k && x[k]!=x[i-1])
		{
			k  = xnext[k];
		}
		xnext[i] = k+1;
	}
}

void makernext(int len)
{
	rnext[1] = 0;
	for (int i = 2,k;i<=len+1;i++)
	{
		k = rnext[i-1];
		while(k && rx[k]!=rx[i-1])
		{
			k  = rnext[k];
		}
		rnext[i] = k+1;
	}
}

bool kmp(int p, int len) // x匹配a[p],len是模式串的长度
{
	int i = 0,j =1;
	while(i<a[p].length())
	{
		while(i<a[p].length() && j<=len && a[p][i]==x[j])
		{
			++i,++j;
		}
		if (j==1)
		{
			++i;
		}
		else
		{
			if (j>len)
			{
				return true;
			}
			j = xnext[j];
		}
	}
	return false;
}

bool rkmp(int p, int len) // rx匹配a[p],len是模式串的长度
{
	int i = 0,j=1;
	while(i<a[p].length())
	{
		while(i<a[p].length() && j<=len && a[p][i]==rx[j])
		{
			++i,++j;
		}
		if (j==1)
		{
			++i;
		}
		else
		{
			if (j>len)
			{
				return true;
			}
			j = rnext[j];
		}
	}
	return false;
}

bool ck(int start, int len) // x=a[0][i,...,i+len-1]
{
	memset(xnext,0,sizeof(xnext));
	memset(rnext,0, sizeof(rnext));
	for (int i=0;i<len;i++)
	{
		x[i+1] = a[0][start+i];
		rx[i+1] = a[0][start+len-i-1];
	}
	makenext(len);
	makernext(len);
	for (int i = 0;i<n;i++) // kmp匹配文本串a[i]
	{
		if (!kmp(i,len) && !rkmp(i,len))
		{
			return false;
		}
	}
	return true;
}

int sol()
{
	sort(a,a+n,cmp);
	m = a[0].length();
	for (int len = m; len; len--) // 枚举X的长度
	{
		for (int i = 0;i<m-len+1;i++) // 枚举X的起点索引, 则X就是 a[0][i,...,i+len-1]
		{
			if (ck(i,len))
			{
				return len;
			}
		}
	}
	return 0;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	int kase;
	cin>>kase;
	while(kase--)
	{
		cin>>n;
		for (int i = 0;i<n;i++)
		{
			cin>>a[i];
		}
		cout << sol() << endl;
	}
	return 0;
}

ac情况

Status Accepted
Memory 192kB
Length 2103
Lang C++
Submitted 2019-10-23 11:37:13
Shared
RemoteRunId 20982310