NSOJ10050 Newspaper Headline
题意：给你一个<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
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#define ll long long
#define maxn 10500
using 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
", cnt);
else printf("-1
");
}
return 0;
}