TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5942
  • Problem
  • P5942基因改造
    Limits : Time Limit : - MS   Memory Limit : - KB
    Description

    "人类智慧的冰峰,只有萌萌哒的我寂寞地守望。"
    --TB
    TB正走在改造人类智慧基因的路上。TB发现人类智慧基因一点也不萌萌哒,导致人类普遍智商过低,为了拯救低智商人群,博爱的TB开始改造人类智慧基因。人类智慧DNA由C种人类智慧脱氧核苷酸构成(这是一种十分特殊的DNA)。

    TB智慧DNA片段T长度为M,她可以把另一段长度为M的人类智慧DNA片段S改造成T。

    改造过程中,TB可以充分发挥智慧,将任意两种人类智慧脱氧核苷酸交换(比如对于片段S=12321,交换1和2变成S=21312,交换1和4变成42324),可以无限次交换。如果S可以通过若干次交换变成T,那么就称S为"萌萌哒人类基因片段"。

    TB想知道对于一个长度为N的人类智慧DNA片段S[1 ~ N],有多少个长度为M的连续子片段S[i ~ i+M-1],是"萌萌哒人类基因片段",并且这些"萌萌哒人类基因片段"在哪里。

    Input Format

    第一行包含两个正整数case和C,分别表示数据组数和人类智慧脱氧核苷酸的种数。

    接下来3*case行,每三行表示一组数据:
    第一行一个正整数N和M,表示人类智慧DNA片段S和TB智慧DNA片段T的长度。
    第二行N个正整数,表示人类智慧DNA片段S。
    第三行M个正整数,表示TB智慧DNA片段T。

    对于所有数据数据,case=3, n,m,C<=100000

    Output Format

    对于每组数据:
    第一行一个正整数tot,表示"萌萌哒人类基因片段"的个数。
    接下来一行tot个用空格隔开的正整数pos,表示"萌萌哒人类基因片段"开头所在的位置。要求从小到大输出每个pos。

    Sample Input

    3 3
    6 3
    1 2 1 2 3 2
    3 1 3
    6 3
    1 2 1 2 1 2
    3 1 3
    6 3
    1 1 2 1 2 1
    3 1 3

    Sample Output

    3
    1 2 4
    4
    1 2 3 4
    3
    2 3 4

    Hint

    对于第一组数据:
    S[ 1 ~ 3]=121,可以先将1和2交换变成212,再将2和3交换变成313。
    S[2 ~ 4]=212,可以将2和3交换变成313。
    S[4 ~ 6]=232,可以先将2和3交换变成323,再将1和2交换变成313。


    Source  bzoj 4641