思路:

kmp + 二分。

实现:

 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = ;
int neXt[MAXN]; void getNext(string s)
{
int n = s.length();
neXt[] = -;
int k = -, j = ;
while (j < n)
{
if (k == - || s[j] == s[k])
{
j++; k++;
if (s[j] != s[k]) neXt[j] = k;
else neXt[j] = neXt[k];
}
else
{
k = neXt[k];
}
}
} int kmp(string s, string p)
{
int i = , j = ;
int m = s.length(), n = p.length();
while (i < m && j < n)
{
if (j == - || s[i] == p[j]) i++, j++;
else j = neXt[j];
}
if (j == n) return i - j;
return -;
} bool solve(string x, string y, vector<pair<int, int>> & ans)
{
string z(x);
reverse(z.begin(), z.end());
int m = x.length();
int n = y.length();
int start = ;
while (start < n)
{
int l = , r = n - start, res = , pos = -;
bool flg = true;
while (l <= r)
{
int mid = (l + r) >> ;
string tmp = y.substr(start, mid);
getNext(tmp);
int p = kmp(x, tmp);
if (p != -)
{
res = mid; pos = p; flg = true; l = mid + ;
}
else if ((p = kmp(z, tmp)) != -)
{
res = mid; pos = p; flg = false; l = mid + ;
}
else r = mid - ;
}
if (!res) return false;
if (flg) ans.push_back(pair<int, int>(pos + , pos + res));
else ans.push_back(pair<int, int>(m - pos, m - pos - res + ));
start += res;
}
return true;
} int main()
{
string x, y;
cin >> x >> y;
vector<pair<int, int>> res;
if (solve(x, y, res))
{
cout << res.size() << endl;
for (int i = ; i < res.size(); i++)
cout << res[i].first << " " << res[i].second << endl;
}
else
{
puts("-1");
}
return ;
}

最新文章

  1. 7. Android框架和工具之 android-percent-support-lib-sample(百分比支持)
  2. 【JSONCpp】简介及demo
  3. 浅谈C中的指针和数组(四)
  4. [LeetCode]题解(python):002-Add Two Numbers
  5. django user模块改写
  6. struts-config.xml的配置
  7. nginx安装文档
  8. css控制div强制换行
  9. .NET(c#) 移动开发平台 - Smobiler(1)
  10. jq slideToggle()坑
  11. 小米平板7.0系统如何不root激活Xposed框架的方法
  12. PHP协程入门详解
  13. 测试创建表变量对IO的影响
  14. Eclipse 中Git的使用及如何解决冲突
  15. SpringBoot 试手(简易的SpringBoot搭建步骤)
  16. 今天通过npm 安装 install 的时候出现的问题
  17. 《Inside C#》笔记(三) 数据类型
  18. etcd raft如何实现leadership transfer
  19. Android -- 仿小米锁屏画报
  20. mysql_connect

热门文章

  1. 戏说云计算之PaaS,IaaS,SaaS
  2. Sql语句中关于如何在like &#39;%?%&#39;中给?赋值
  3. dubbo 学习1
  4. Ubuntu 16.04安装PDF阅读器FoxitReader
  5. 条款31: 千万不要返回局部对象的引用,也不要返回函数内部用new初始化的指针的引用
  6. UIView convertRect
  7. 算法竞赛入门经典 习题 2-10 排列(permutation)
  8. 第二课 MongoDB 数据模型
  9. ALSA声卡驱动中的DAPM详解之七:dapm事件机制(dapm event)
  10. go语言笔记——切片底层本质是共享数组内存!!!绝对不要用指针指向 slice切片本身已经是一个引用类型就是指针