原本就想到dp,可是是我的思路是在串的各个位置都遍历一次set,看dp[i-st[k]]是否为1且前length(st[k])是st[k]。这样200000*200*10会超时。更好的办法是在i位取前len<=10个看dp[]和set中是否存在。只要200000*55*log200。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#define mkp make_pair
using namespace std;
const double EPS=1e-;
typedef long long lon;
const lon SZ=,INF=0x7FFFFFFF;
set<string> st;
string str;
int arr[SZ]; void init()
{
for(;;)
{
string tmp;
cin>>tmp;
if(tmp==".")break;
st.insert(tmp);
}
string tmp;
for(;cin>>tmp;)
{
str+=tmp;
}
} void work()
{
int res=;
for(int i=;i<str.size();++i)
{
for(int j=;j<=;++j)
{
if(i-j-<||arr[i-j-])
{
string tmp=str.substr(max(,i-j),min(i+,j+));
//if(i==6)cout<<j<<" "<<tmp<<" "<<(st.find(tmp)!=st.end())<<endl;
if(st.find(tmp)!=st.end())
{
arr[i]=;
//cout<<i<<" "<<"here"<<endl;
break;
}
}
}
if(arr[i]==)
{
res=i+;
}
}
cout<<res<<endl;
} int main()
{
std::ios::sync_with_stdio();
//freopen("d:\\1.txt","r",stdin);
lon casenum;
//cin>>casenum;
//for(lon time=1;time<=casenum;++time)
{
init();
work();
}
return ;
}

最新文章

  1. 【读书笔记】WebApi 和 SPA(单页应用)--knockout的使用
  2. MongoDB使用汇总贴
  3. linux+apache url大小写敏感问题
  4. 平衡二叉树,AVL树之图解篇
  5. IIS7 Appcmd.exe 使用
  6. 夺命雷公狗---node.js---6net模块玩telnet通信(下)
  7. Lessons learned from manually classifying CIFAR-10
  8. typeerror $.ajax is not a function
  9. Python学习笔记四,dict和set
  10. Linux中iptables设置详细
  11. java中表示二进制、八进制、十进制、十六进制
  12. docker服务各个模块
  13. NTSC、PAL、SECAM三大制式简介
  14. [js]js中类的继承
  15. SRS用例
  16. laravel 服务容器实例——深入理解IoC模式
  17. SPARK数据类型
  18. gcc 与 g++的区分较
  19. tomcat发布html静态页面
  20. WPF 卡顿调试经验

热门文章

  1. topcoder srm 662 div1
  2. Python3 tkinter基础 Label pack 设置控件在窗体中的位置
  3. Win10子系统Ubuntu安装llvm+clang
  4. Spring Boot 2 入门
  5. p3168 [CQOI2015]任务查询系统(差分+主席树)
  6. zepto 入门
  7. 3、Python迭代器、列表解析及生成器(0530)
  8. HDU 5459 Jesus Is Here(递推)
  9. Codeforces 510 E. Fox And Dinner
  10. 浅谈Java中的栈和堆