ウイルス侵襲(HDU_2896)ACオートマトン(Trie図)
ウイルスの侵襲
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19067 Accepted Submission(s): 4715
Problem Description
太陽の輝きが月に遮られ、世界は光を失い、大地は最も暗い時を迎える...こんな時、人々はとても興奮しています.私たちは生きている間に500年に一度の世界の奇観を見ることができます.それはどんなに幸せなことですか.
しかし、ネット上には好奇心を借りて日食を紹介するという旗印を掲げ、ウイルスを広めているサイトがある.tちゃんは不幸にも被害者の一人になった.tさんはこのように怒って、彼は世界のすべてのウイルスのウェブサイトを探し出すことにした.もちろん、それは不可能だと誰もが知っています.tちゃんはこのできない任務を果たすことに固執し、「子々孫々が尽きない!」(愚公の後継者がいる)と言った.
何事も初めが難しいので、tさんは多くのウイルスの特徴コードを集めて、またいくつかの奇妙なサイトのソースコードを集めて、彼はこれらのサイトの中でどれがウイルスがあるのか、またどんなウイルスを持っているのか知りたいと思っています.ついでに、彼がどれだけウイルスを持ったサイトを集めたのか知りたい.この時彼は何から手をつけたのか分からなかった.だから皆さんに手伝ってもらいたいです.tちゃんはまたせっかちなので、問題を解決するのが早ければ早いほどいいですよ~~
Input
1行目は、ウイルス特徴コードの個数を表す整数N(1<=N<=500)である.
次のN行は、各行がウイルス特徴コードを表し、特徴コード文字列の長さは20〜200の間である.
各ウイルスには1～Nの番号が付けられています.
異なる番号のウイルスフィーチャーコードは同じではありません.
その後の行には、サイト数を表す整数M(1<=M<=1000)がある.
次にM行、各行は1つのウェブサイトのソースコードを表し、ソースコード文字列の長さは7000~10000の間である.
各サイトには1～Mの番号があります.
上記の文字列の文字はすべてASCIIコードの可視文字です(リターンは含まれません).
Output
以下のフォーマットで出力し、サイト番号で小さいから大きいまで出力し、ウイルス付きのサイト番号とウイルス番号を含み、各行に1つの毒入りサイト情報を出力します.
Webサイト番号:ウイルス番号ウイルス番号...
コロンの後にスペースがあり、ウイルス番号は小さいものから大きいものに並べられ、2つのウイルス番号の間には1つのスペースで区切られています.1つのサイトにウイルスが含まれている場合、ウイルス数は3つを超えません.
最後の行は、次のフォーマットで統計を出力します.
total:ウイルス付きサイト数
コロンの後ろにスペースがあります.
Sample Input
Sample Output
いくつかのパターン列を与えて、もう一つの主列を与えて、パターン列が主列に現れる回数を求めます;
問題を解く構想:ACオートマチック.
コード#コード#
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19067 Accepted Submission(s): 4715
Problem Description
太陽の輝きが月に遮られ、世界は光を失い、大地は最も暗い時を迎える...こんな時、人々はとても興奮しています.私たちは生きている間に500年に一度の世界の奇観を見ることができます.それはどんなに幸せなことですか.
しかし、ネット上には好奇心を借りて日食を紹介するという旗印を掲げ、ウイルスを広めているサイトがある.tちゃんは不幸にも被害者の一人になった.tさんはこのように怒って、彼は世界のすべてのウイルスのウェブサイトを探し出すことにした.もちろん、それは不可能だと誰もが知っています.tちゃんはこのできない任務を果たすことに固執し、「子々孫々が尽きない!」(愚公の後継者がいる)と言った.
何事も初めが難しいので、tさんは多くのウイルスの特徴コードを集めて、またいくつかの奇妙なサイトのソースコードを集めて、彼はこれらのサイトの中でどれがウイルスがあるのか、またどんなウイルスを持っているのか知りたいと思っています.ついでに、彼がどれだけウイルスを持ったサイトを集めたのか知りたい.この時彼は何から手をつけたのか分からなかった.だから皆さんに手伝ってもらいたいです.tちゃんはまたせっかちなので、問題を解決するのが早ければ早いほどいいですよ~~
Input
1行目は、ウイルス特徴コードの個数を表す整数N(1<=N<=500)である.
次のN行は、各行がウイルス特徴コードを表し、特徴コード文字列の長さは20〜200の間である.
各ウイルスには1～Nの番号が付けられています.
異なる番号のウイルスフィーチャーコードは同じではありません.
その後の行には、サイト数を表す整数M(1<=M<=1000)がある.
次にM行、各行は1つのウェブサイトのソースコードを表し、ソースコード文字列の長さは7000~10000の間である.
各サイトには1～Mの番号があります.
上記の文字列の文字はすべてASCIIコードの可視文字です(リターンは含まれません).
Output
以下のフォーマットで出力し、サイト番号で小さいから大きいまで出力し、ウイルス付きのサイト番号とウイルス番号を含み、各行に1つの毒入りサイト情報を出力します.
Webサイト番号:ウイルス番号ウイルス番号...
コロンの後にスペースがあり、ウイルス番号は小さいものから大きいものに並べられ、2つのウイルス番号の間には1つのスペースで区切られています.1つのサイトにウイルスが含まれている場合、ウイルス数は3つを超えません.
最後の行は、次のフォーマットで統計を出力します.
total:ウイルス付きサイト数
コロンの後ろにスペースがあります.
Sample Input
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc
Sample Output
web 1: 1 2 3
total: 1
いくつかのパターン列を与えて、もう一つの主列を与えて、パターン列が主列に現れる回数を求めます;
問題を解く構想:ACオートマチック.
コード#コード#