Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 2 KB
package welcometocodejamszk;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
public class fg_welcome2 {
public static void main(String[] args) throws IOException {
new fg_welcome2().run();
}
String sub, main;
int accel[][];
int count(int subPos, int mainPos) {
if (accel[subPos][mainPos] >= 0) {
return accel[subPos][mainPos];
}
int res = 0;
if (subPos == sub.length()) {
res = 1;
} else if (mainPos == main.length()) {
res = 0;
} else {
if (mainPos < main.length() - 1) {
res = res + count(subPos, mainPos+1);
}
if (main.charAt(mainPos) == sub.charAt(subPos)) {
res = res + count(subPos+1, mainPos+1);
}
}
accel[subPos][mainPos] = res % 10000;
return accel[subPos][mainPos];
}
void doubleFill(int[][] x, int val) {
for (int j = 0; j < x.length; j++) {
Arrays.fill(x[j], -1);
}
}
int solve() {
accel = new int[sub.length()+1][main.length()+1];
doubleFill(accel, -1);
return count(0, 0);
}
void run() throws IOException {
String code = "large";
BufferedReader br = new BufferedReader(new FileReader("C-"+code+".in"));
PrintWriter pw = new PrintWriter(new FileWriter("C-"+code+".out"));
sub = br.readLine();
int N = Integer.parseInt(br.readLine());
for (int i = 1; i <= N; i++) {
main = br.readLine();
int res = solve();
pw.printf("Case #%1$d: %2$04d\n", i, res);
}
br.close();
pw.close();
}
}