HNUSTOJ-1543 字符串的运算再现

HNUSTOJ-1543 字符串的运算再现

大家好,又见面了,我是全栈君。

 

1543: 字符串的运算再现

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 7
[提交][状态][讨论版]

题目描述

我们对字符串 S 做了以下定义:

1. S ^ k表示由k个字符串S构成的新字符串。 例如, S = “abc”, k = 3, 则S ^ k  =  “abcabcabc”

2. Subsequence(S) 表示由字符串S的所有非空子序列构成的字符串集合。例如, S = “abc”, 则Subsequence(S) = {“a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”}

现在, 给你2个字符串S和T, 希望你能找到最小的k, 满足T ∈Subsequence(S ^ k)

 

输入

输入只有2行, 分别为字符串S和T (1 <= |S|, |T| <= 100,000), 输入保证字符串S和T只由小写字母构成。

 

输出

输出最小的k, 满足T ∈Subsequence(S ^ k), 若不存在这样的k, 则输出-1

 

样例输入

abc
abacbc

样例输出

3
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#include <typeinfo>


using namespace std;
const int N =  100000 + 5;

char s[N], t[N];


void Init(int * a, int n){ for(int i = 0; i < n; i++) a[i] = 0;}
int Work(){
    int lens = strlen(s), lent = strlen(t);
    set<int> next[26];
    int vis[26]; Init(vis, 26);
    for(int i = 0 ; i < lens; i++)
        vis[s[i] - 'a'] = 1, next[s[i]-'a'].insert(i);

    for(int i = 0; i < lent; i++) if(!vis[t[i]-'a']) return -1;

    int cur = 0, k = 1;

    set<int>::iterator it;

    for(int i = 0; i < lent; i++){
        int p = t[i] - 'a';
        if((it = next[p].lower_bound(cur)) != next[p].end()) cur = (*it) + 1;
        else cur = 0, k++, i--;
    }
    return k;
}
int main(){ _
    while(cin >> s >> t){
        cout << Work() << endl;
    }
}

 

转载于:https://www.cnblogs.com/Pretty9/p/7424087.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108210.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • oracle srvctl命令,Oracle SRVCTL使用说明

    oracle srvctl命令,Oracle SRVCTL使用说明SRVCTL是Oracle9iRAC集群配置管理的工具。本文是对SRVCTL的所有命令进行详细说明的一篇参考文档。添加数据库或实例的配置信息。在增加实例中,与-i一起指定的名字应该与INSTANCE_NAME和ORACLE_SID参数匹配。srvctladddatabase-ddatabase_name[-mdomain_name]-ooracle_home[-sspfi…

  • python画图[通俗易懂]

    python画图[通俗易懂]Matplotlibpython图形可以分为两部分。一个是外部的整体设置,比如坐标轴的设置,注释,透明度等;一个是内部具体图形,不同图形可能大同小异。外部设置,是我们需要掌握的内容。内部具体图形的操作,用的时候搜索下就好。

  • 数据库表结构设计[通俗易懂]

    数据库表结构设计[通俗易懂]为什么要学习数据表结构设计实际开发中,需要根据需求,将实际模型转换成物理表结构,这时需要考虑几个问题,表名称如何命名,表中需要哪些字段,各个字段的命名规范,字段的数据类型,字段的长度,和其他表的联系,这些都是需要考虑的。推荐使用的工具PowerDesigner这个工具,可以做UUML图帮助分析数据关系,最重要的是可以把设计好的表结构转换成你使用的数据库的命令语句,方便在数据库中使用…

  • 常用C#代码「建议收藏」

    常用C#代码「建议收藏」常用C#代码字符串处理1.字符串截取//字符串截取//从此实例检索子字符串。子字符串从指定的字符位置开始且具有指定的长度。string.Substring(intindex,intlength);//从此实例检索子字符串。子字符串在指定的字符位置开始并一直到该字符串的末尾。string.Substring(intindex);2.字符串分割//字符串分割//separator-char类型的数组分隔符,例:newchar[]{‘,’,‘|’}string.Split

  • Java 方法

    Java 方法

  • jira使用教程_jira 工具

    jira使用教程_jira 工具JIRA使用教程:在Windows上安装JIRA JIRA使用教程:在Linux上安装JIRA JIRA使用教程:使用文件包安装JIRA JIRA使用教程:创建项目 JIRA使用教程:创建问题 JIRA使用教程:搜索问题 JIRA使用教程:编辑项目键 JIRA使用教程:简单问题跟踪 JIRA使用教程:创建软件开发项目 JIRA使用教程:共享搜索结果 JIRA使用教程:查看项目…

    2022年10月21日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号