Hello everyone! I need help in this problem!

LINK to the problem.

There are two strings s and t. Find the longest string which is a substring of s and t. If there are many solutions print the first one appear in the string t.

I am one of the coders who use suffix array to solve this problem but got WAs. And the editorial to this question mentioned two ways to solve the problem without suffix array. And it's really annoying that I still don't get why my code was wrong after read the DISCUSS about this.

Please help me! Can you challenge my code?

I'd like to explain my solution first so that you can come up with some test cases that my code will fail.First as the typical suffix array's solution will do, I calculate the suffix array and lcp array of the connected string which is sa[] and hg[] in my code. Then I use binary search to get the length of the answer and get the position in the mean time. And each time check if there's a substring whose length is bigger or equal to the number we check right now. During this I separate the array of lcp into many groups each is a group consists of continued hg[i] which is bigger or equal to the number wo check right now. And if there is a group in which there is a sa[i] < ls and another sa[j] > ls, then the number we check right now is OK. (Ps, ls is the length of the first string.)This solution work in O(nlogn) I think.

Here is my code.

Is there any mistake? Please enlighten me. Thanks a lot.

As the title said, I can't solve this problem even if I've read the tutorial. I can understood the idea of dp[x], the part that dp[x] is a monotone increasing function. But I can't figure out how to use it to solve the problem. Naive implement will cause TLE. Any hint? Thank you in advance. Here's the LINK to the problem.

LIS, Longest Increasing Subsequence for short.

LCS, Longest Common Subsequence for short.

LPS, Longest Palindrome Subsequence for short.(Ps, I don't konw if it's an official name.)

There're many problems on Codeforces are about these classical problems, such as 335B,340D and so on. Let's discuss the algos to solve all these prolems.

Note that, we'd like to count the length of the sequence and also we want to get a valid subsequence of the original sequence.(maybe the leftest one, or that has the smallest alphabet order.sorry for my poor English.)

As far as I know, LIS can be sloved in O(nlogn). algo goes like this. For example, 2 1 5 4 3 7 8 6 9, we can use a array to save the LIS we can get until now, and every time we come up with a new number. We find the leftest number which if smaller than it, and replace the next one with the num we have right now. array changes like this:

2 -> 1 -> 1 5 -> 1 4 -> 1 3 -> 1 3 7 -> 1 3 7 8 -> 1 3 6 8 -> 1 3 6 8 9.

So, length we want is 5. And you can check it out.(2 5 7 8 9 is an valid subsequence with length 5.) this algo runs in O(nlogn). Use binary search (you can use lower_bound() in STL in convenience.)to find the right place where we want to put the number we have right now.

What I know is so limited, so be my guest and share your ideas to these problems.(Ps, I don't know how to find a valid subsequence of the problem above, as you can see, the alog doesn't give the right subsequence we want.)

Thank you sincerely. And I'm sorry that I don't konw how to make this blog look more neatly rather than all the words gathered together, though I have tried all my best to tap the end of line, however when it was posted, it doesn't work. I'm not very familiar with this skills.(If you can help me with this problem, that will be lovely!)

Time Limit: 3000ms Memory Limit: 65536kb Description Now, you are given three positive A, B, C, your task is to compute the first B digits and the last C digits of the factorial of A. For example A=5, B=2, C=1. Then A! =120, so you should output 12 0 separated by one blank. Input The first line, an integer T, representing T test cases below. (T<=200). Each test case contains three integers: A (1<=A<=10^8), B (1<=B<=50) and C (1<=C<=100). Notice: No illegal case is permitted. For example, the condition A=4, B=10, C=10 is not permitted in the input data. Output For each case, output the first B digits and the last C digits of the factorial of A separated by one blank. Sample Input 2 5 2 1 8 2 2 Sample Output 12 0 40 20

I've no idea about calculating the first B digits of the factorial. Please help.Thank you. If you want to submit your code , here is the link. http://acm.ustc.edu.cn/ustcoj/problem.php?id=1265 Anybody interested？