تبدیل Burrows-Wheeler

Time Limit: 10 Seconds    Memory Limit: 65536 KB

فرض کنید برای یک دنباله‌ی ژنوم (genome)، رشته‌ی Burrows-Wheeler Transform یا BWT آن بعد از اعمال روش فشرده‌سازی «طول‌دنباله» (run-length encoding) داده شده. مثلا رشته‌ی ACCTGAACTGTG را در نظر بگیرید. دنباله‌ی BWT آن برابر است با GG$AACATTTGCC زیرا:

$ACCTGAACTGTG

AACTGTG$ACCTG

ACCTGAACTGTG$

ACTGTG$ACCTGA

CCTGAACTGTG$A

CTGAACTGTG$AC

CTGTG$ACCTGAA

G$ACCTGAACTGT

GAACTGTG$ACCT

GTG$ACCTGAACT

TG$ACCTGAACTG

TGAACTGTG$ACC

TGTG$ACCTGAAC

بنابراین بعد از فشرده‌سازی رشته‌ی 2G1$2A1C1A3T1G2C به دست می‌آید. هدف ما این است که با گرفتن این رشته و یک عدد k، تعداد kتایی‌های (k-mers) یکتا در رشته‌ی اصلی را مشخص کنیم. به‌عنوان نمونه، برای مثال بالا، اگر k=۳ باشد، پاسخ برابر ۹ است (توجه کنید که ۳تایی CTG دوبار تکرار شده است).

برنامه‌ای بنویسید که با دریافت رشته‌ی BWT ورودی و یک عدد k، تعداد kتایی‌های یکتا در رشته‌ی اصلی را مشخص کند. ورودی و خروجی مسئله از ورودی و خروجی استاندارد (stdin و stdout) است با قالب زیر:

ورودی: سطر اول ورودی یک عدد T < ۲۰ نوشته شده که تعداد رشته‌های ورودی است. بعد از آن به ازاء هر ورودی در سطر اول عدد k و بعد از آن یک عدد L نوشته شده که تعداد زوج‌هایی است که رشته‌ی ورودی را مشخص می‌کند (می‌توانید فرض کنید که طول کل رشته‌ی اصلی ژنوم حداکثر یک میلیون حرف است). بعد از آن در L سطر بعدی، در هر سطر یک زوج عدد و حرف نوشته شده (مثال زیر را ببینید).

خروجی: به ازاء هر داده‌ی ورودی یک خط خروجی وجود دارد که در آن یک عدد نوشته شده برابر با تعداد kتایی‌های یکتا در رشته‌ی اصلی.

Sample Input

2
3 8
2 G
1 $
2 A
1 C
1 A
3 T
1 G
2 C
2 11
1 G
1 $
1 T
1 C
1 G
1 C
2 A
1 C
1 A
1 T
1 A

Sample Output

9
9

Submit