E.Text Editor （Gym 101466E + 二分 + kmp)

题目链接：http://codeforces.com/gym/101466/problem/E

题目：

题意：

　　给你s串和t串，一个数k，求t的最长前缀串在s串中出现次数不少于k。

思路：

　　一眼二分+kmp，二分最长前缀串的长度即可。

代码实现如下：

 1 #include <set>
 2 #include <map>
 3 #include <queue>
 4 #include <stack>
 5 #include <cmath>
 6 #include <bitset>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 
16 typedef long long ll;
17 typedef pair<ll, ll> pll;
18 typedef pair<ll, int> pli;
19 typedef pair<int, ll> pil;;
20 typedef pair<int, int> pii;
21 typedef unsigned long long ull;
22 
23 #define lson i<<1
24 #define rson i<<1|1
25 #define lowbit(x) x&(-x)
26 #define bug printf("*********
");
27 #define debug(x) cout<<"["<<x<<"]" <<endl;
28 #define FIN freopen("D://code//in.txt", "r", stdin);
29 #define IO ios::sync_with_stdio(false),cin.tie(0);
30 
31 const double eps = 1e-8;
32 const int mod = 1e9 + 7;
33 const int maxn = 1e5 + 7;
34 const double pi = acos(-1);
35 const int inf = 0x3f3f3f3f;
36 const ll INF = 0x3f3f3f3f3f3f3f3f;
37 
38 int k, lens1, lens2, ans, num;
39 char s1[maxn], s2[maxn];
40 int nex[maxn];
41 
42 void get_next() {
43     nex[1] = 0;
44     for(int i = 2, j = 0; i <= lens2; i++) {
45         while(j > 0 && s2[i] != s2[j+1]) j = nex[j];
46         if(s2[i] == s2[j+1]) j++;
47         nex[i] = j;
48     }
49 }
50 
51 void kmp() {
52     get_next();
53     for(int i = 1, j = 0; i <= lens1; i++) {
54         while(j > 0 && (j == lens2 || s1[i] != s2[j+1])) j = nex[j];
55         if(s1[i] == s2[j+1]) j++;
56         if(j == lens2) {
57             num++;
58         }
59     }
60 }
61 
62 bool check(int x) {
63     lens2 = x;
64     num = 0;
65     kmp();
66     return num >= k;
67 }
68 
69 int main() {
70     fgets(s1 + 1, maxn, stdin);
71     fgets(s2 + 1, maxn, stdin);
72     scanf("%d", &k);
73     lens1 = strlen(s1 + 1), lens2 = strlen(s2 + 1);
74     int ub = lens2, lb = 0, mid;
75     ans = 0;
76     while(ub >= lb) {
77         mid = (ub + lb) >> 1;
78         if(check(mid)) {
79             ans = mid;
80             lb = mid + 1;
81         } else {
82             ub = mid - 1;
83         }
84     }
85     if(ans > 0) {
86         for(int i = 1; i <= ans; i++) {
87             printf("%c", s2[i]);
88         }
89         printf("
");
90     }
91     else printf("IMPOSSIBLE
");
92     return 0;
93 }