CF79C Beaver

Cho n xâu b1,b2,..,bn được xem là boring và xâu S. Tìm substring dài nhất của S ko chứa n xâu boring như là substring

(n<=10, |S|<=10^5)

Sample test(s)

input

Go_straight_along_this_street
5
str
long
tree
biginteger
ellipse

output

12 4

input

IhaveNoIdea
9
I
h
a
v
e
N
o
I
d

output

0 0

input

unagioisii
2
ioi
unagi

output

5 5

Algorithm:

Nhận xét với đoạn substring (i,j) của S, nếu (i,j) không thỏa mãn thì (i,j+1) (i,j+2) ... cũng không thỏa mãn và (i+1,j) (i+2,j) ... cũng không thỏa mãn. Điều này làm ta nghĩ đến thuật toán twopointers

dau=cuoi=0;
len=s.length();
luu=res=0;

while (dau<=len-1)
{
//cuoi=dau;
while (cuoi<=len-1 && ok(dau,cuoi))
{
cuoi++;
}
if (res<cuoi-dau)
{
res=cuoi-dau;
luu=dau;
}
if (dau==cuoi) dau++;
else
{
dau++;
while (!ok(dau,cuoi)) dau++;
}
}