遇到不会的问题了,求解答
  • 板块学术版
  • 楼主dqe233
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/22 19:29
  • 上次更新2024/7/22 20:25:05
查看原帖
遇到不会的问题了,求解答
1347247
dqe233楼主2024/7/22 19:29

题目描述 给出一个长度为N的整数串A,和一个长度为K的整数串B,A和B中的元素均是不大于S的正整数。

我们认为两个串是相等的,当两个串的长度相当,并且两个串中,对于任意的i,第i个元素在两个串中的排名是一样的。

例如:

1 2 3 5 4 8 10 23 25 24 这两个串是相等的。

现在要求在A的所有长度=B的长度的子串中,有多少子串与B串相等。

输入格式 第一行三个整数N,K,S , , 。

第二行N个整数表示A串。

第三行K个整数表示B串。

输出格式 第一行一个P表示A串中一共有多少个子串和B串相等。 接下来P行从小到大每行一个整数,表示和B串相等的A串的子串的第一个元素的位置。

样例:

样例输入: 9 6 10 5 6 2 10 10 7 3 2 9 1 4 4 3 2 1

样例输出: 1 3

数据范围与提示 对于20%的数据N<=10000 对于100%的数据1<=N<=500000,S<=10000

一本通上的题,是KMP那章的,不知各位有没有解决办法(一本通丢了,没法看课本)

2024/7/22 19:29
加载中...