题意：给你一个<10^4的S串和<10^6的T串，通过将S串重复k次，然后将其中一些多余的字母删掉可以获得T串，问k最小是多少，没有的话输出1.
思路：对于每个T串里的字母，我们从左到右扫，由于我们一定要找到对应的字母，于是我们必然是尽可能早的在S串里找到这个字母，然后再从匹配的串的位置开始继续往后找T串的下一个字母。所以贪心的思路就是我们总是尽量在S串的前面匹配到T的对应字母。
譬如样例 S:abcd T:dabc, 首先我们肯定要匹配d，所以我们一开始将指针移到S的d的位置，然后发现往后不能再匹配了，然后又回到串首，发现可以匹配d的下一个a,然后从a开始又能匹配下一个b，类似的我们就可以匹配完全部的字母了，然后得出最少的次数。
实现的话其实也不困难，我们可以建一个类似自动机的东西，S串的每个字母相当于一个状态，然后对每个字母我们推算出其下一个最近的a,b,c,d...z在哪个位置。实现的方法很简单，开一个vector<int> alpha[26],alpha[i]存的是第i个字符的所有下标，所以每次找的时候就一个upper_bound就可以了。然后就在这个自动机上走就是了，每次走到NULL结点的时候cnt++. 如果当前在根结点仍然不能往下匹配到下一个T串的点的时候就说明是-1。
题目还是挺简单的，不知道为什么当时没什么人过，赛后也没什么人做。。－ －0
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<vector>#include<cstdio>#include<algorithm>#include<cmath>#include<string>#define ll long long#define maxn 10500using
namespace std;char
S[maxn];char
T[maxn*100];struct
Node{ Node *go[26]; void
init() { memset(go, 0, sizeof(go)); }}pool[maxn];Node *root;vector<int> alpha[26];vector<int>::iterator it;int
main(){ while
(~scanf("%s%s", S, T)) { int
lens = strlen(S); pool[0].init(); root = &pool[0]; for
(int i = 0; i < 26; i++) { alpha[i].clear(); alpha[i].push_back(0); } for
(int i = 0; i < lens; i++){ pool[i + 1].init(); alpha[S[i] - ‘a‘].push_back(i + 1); } for
(int i = 0; i <= lens; i++){ for
(int j = 0; j < 26; j++){ it = upper_bound(alpha[j].begin(), alpha[j].end(), i); if
(it == alpha[j].end()) continue; else
pool[i].go[j] = &pool[*it]; } } int
cnt = 0; int
lent = strlen(T); Node *p = NULL; bool
flag = true; int
i = 0; while(i<lent){ if
(p == NULL) cnt++, p = root; if
(p == root&&p->go[T[i] - ‘a‘] == NULL) { flag = false; break; } p = p->go[T[i] - ‘a‘]; if
(p != NULL) i++; } if
(flag) printf("%d\n", cnt); else
printf("-1\n"); } return
0;} |
NSOJ10050 Newspaper Headline,布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3585069.html