Can you do it better

All submissions for this problem are available.
Your task is to write a program which computes exactly the same result as Chef's programs below. He was kind enough to provide you with the same program written in three different programming languages. However, your solution should be much faster.
C++
#include <iostream> #include <string> using namespace std; int main() { string a, b, c; int na, nb, r; cin >> a; na = a.size(); cin >> b; nb = b.size(); cin >> c; r = 0; for (int i = 0; i < nb; i++) { for (int j = 1; j < min(na+1, nbi+1); j++) { bool f = true; int d = 0; for (int k = 0; k < j; k++) { if (a[k] != b[i+k]) { if (c[k] == '1') { d += 1; } else { f = false; } } } if (f && d <= 2) { r = (r + j*j) % 1000000007; } } } cout << r << endl; return 0; }
Java
import java.util.Scanner; public class Main { static String a, b, c; static int na, nb, r; public static void main(String[] args) { Scanner sc = new Scanner(System.in); a = sc.next(); na = a.length(); b = sc.next(); nb = b.length(); c = sc.next(); r = 0; for (int i = 0; i < nb; i++) { for (int j = 1; j < Math.min(na+1, nbi+1); j++) { boolean f = true; int d = 0; for (int k = 0; k < j; k++) { if (a.charAt(k) != b.charAt(i+k)) { if (c.charAt(k) == '1') { d += 1; } else { f = false; } } } if (f && d <= 2) { r = (r + j*j) % 1000000007; } } } System.out.println(r); } }
Python
a = raw_input() na = len(a) b = raw_input() nb = len(b) c = raw_input() r = 0 for i in range(nb): for j in range(1, min(na+1, nbi+1)): f = True d = 0 for k in range(j): if (a[k] != b[i+k]): if (c[k] == '1'): d +=1 else: f = False if (f and d <= 2): r = (r + j*j) % 1000000007 print r
Input
The strings A, B and C are provided in a compressed form to keep the input small enough. Sequence 00000 is encoded with letter 'a', 00001 with 'b' and so on until 'z'. 11010 is represented by 'A' and 11111 by 'F'.
The input consists of three lines of letters az, AF. First line contains at most 200 characters and the second one at most 2 000 000. Third line has the same length as the first line and will contain at most 40 digits 1 when decompressed.
Example
Input: aBFn ygFBg bbdb Output: 2990
Explanation
After decompression we get strings 00000110111111101101, 1100000110111111101100110 and 00001000010001100001. If we run chef's program with this decompressed input, we will get 2990 as a result.
Author:  thocevar 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/CYDB 
Tags  feb12, hard, thocevar 
Date Added:  4122011 
Time Limit:  0.334218 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 