浙江财经大学
信息管理与工程学院

Codeforces 91 A/90 C. Newspaper Headline

本文由 Ocrosoft 于 2016-10-21 10:40:33 发表

A newspaper is published in Walrusland. Its heading is s1, it consists of lowercase Latin letters. Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue them one to another in order to get one big string. After that walrus erase several letters from this string in order to get a new word s2. It is considered that when Fangy erases some letter, there’s no whitespace formed instead of the letter. That is, the string remains unbroken and it still only consists of lowercase Latin letters.

For example, the heading is “abc“. If we take two such headings and glue them one to the other one, we get “abcabc“. If we erase the letters on positions 1 and 5, we get a word “bcac“.

Which least number of newspaper headings s1 will Fangy need to glue them, erase several letters and get word s2?

Input

The input data contain two lines. The first line contain the heading s1, the second line contains the word s2. The lines only consist of lowercase Latin letters (1 ≤ |s1| ≤ 104, 1 ≤ |s2| ≤ 106).

Output

If it is impossible to get the word s2 in the above-described manner, print “-1” (without the quotes). Otherwise, print the least number of newspaper headings s1, which Fangy will need to receive the word s2.

Examples
input
abc
xyz

output
-1

input
abcd
dabc

output
2

input

题意:给出两个字符串:a和b,如果能将n个a拼接起来,划去一些字母后(可以不划去),可以得到b,那么输出最小的n,否则输出-1。
思路:
1.记录a有的字母,如果b有的字母a没有,那么就是-1。
2.记录a中每个字母的索引(位置),使用26个set比较方便。
然后对b的每一个字母进行匹配,同时还要记录一下上一个字母匹配到的位置last(初始化-1)。
如果下一个字母匹配的时候如果last比这个字母所有的索引都大,说明要再拼接一个a字符串,也就是答案加一。
否则,选择大于last的第一个位置进行匹配。
这个操作可以使用upper_bound函数,返回大于last的位置,也可以不用,手动二分。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 150 + 10;
const int MOD = 100000;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
int main()
{
	string a,b;cin>>a>>b;
	set<int> s[30];
	int la=a.size(),lb=b.size();
	for(int i=0;i<la;i++)s[a[i]-'a'].insert(i);
	int last=-1,ans=1;
	for(int i=0;i<lb;i++)
	{
		int ch=b[i]-'a';
		if(s[ch].empty()){printf("-1\n");return 0;}
		set<int>::iterator  t=s[ch].upper_bound(last);
		if(t==s[ch].end()){last=-1;ans++;}
		last=*s[ch].upper_bound(last);
	}
	printf("%d\n",ans);
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » Codeforces 91 A/90 C. Newspaper Headline

点赞 (1)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址