fork download
copy 
  1. class Solution {
  2.     long MOD = (long)1e9+7;
  3.     public int findGoodStrings(int n, String s1, String s2, String evil) {
  4.         int[] lps = lps(evil);
  5.         int m = evil.length();
  6.         int[][] to = new int[m][26];
  7.         //to[i][ch] = Longest suffix of string (evil[0, i]+ch), where ch is a character
  8.         for(int i = 0; i< m; i++){
  9.             for(char ch = 'a'; ch <= 'z'; ch++){
  10.                 if(evil.charAt(i) == ch)to[i][ch-'a'] = i+1;
  11.                 else if(i != 0)to[i][ch-'a'] = to[lps[i-1]][ch-'a'];
  12.             }
  13.         }
  14.         long[][] DP = new long[1+n][m];
  15.         //DP[i][j] = Number of ways to choose suffix of length i if the prefix had last j characters same as prefix of evil string
  16.         for(int i = 0; i< m; i++)DP[0][i] = 1;
  17.         for(int len = 1; len <= n; len++){
  18.             for(int prefix = 0; prefix < m; prefix++){
  19.                 for(char ch = 'a'; ch <= 'z'; ch++){
  20.                     int cur = to[prefix][ch-'a'];
  21.                     if(cur < m){
  22.                         DP[len][prefix] += DP[len-1][cur];
  23.                         if(DP[len][prefix] >= MOD)DP[len][prefix] -= MOD;
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.         Counter countingInterface = new Counter(n, s1, s2, evil, to, DP);
  29.         return (int)countingInterface.count();
  30.     }
  31.     class Counter{
  32.         String lo, hi, evil;
  33.         int[][] to;
  34.         int n;
  35.         long[][] DP;
  36.         public Counter(int n, String lo, String hi, String evil, int[][] to, long[][] DP){
  37.             this.lo = lo;this.hi = hi;this.evil = evil;this.to = to;this.n = n;this.DP = DP;
  38.         }
  39.         public long count(){
  40.             return count(0, 3, 0);
  41.         }
  42.         //Digit DP styke function
  43.         private long count(int idx, int flag, int prefix){
  44.             if(idx == n)return 1;
  45.             if(flag == 0)return DP[n-idx][prefix];
  46.             //if the prefix of current string is same as string lo, flag has first bit set
  47.             char lower = (flag&1)==1?lo.charAt(idx):'a';
  48.             //if the prefix of current string is same as string hi, flag has second bit set
  49.             char upper = (flag&2)==2?hi.charAt(idx):'z';
  50.             long ans = 0;
  51.             for(char cur = lower; cur <= upper; cur++){
  52.                 if(to[prefix][cur-'a'] < evil.length()){
  53.                     ans += count(idx+1, (flag&(cur == lower?1:0))|(flag&(cur==upper?2:0)), to[prefix][cur-'a']);
  54.                     if(ans >= MOD)ans -= MOD;
  55.                 }
  56.             }
  57.             return ans;
  58.         }
  59.     }
  60.     //Prefix function
  61.     int[] lps(String pat){
  62.         int m = pat.length();
  63.         int[] lps = new int[m];
  64.         int len = 0, pos = 1;
  65.         while(pos < m){
  66.             if(pat.charAt(pos) == pat.charAt(len))lps[pos++] = ++len;
  67.             else if(len > 0)len = lps[len-1];
  68.             else pos++;
  69.         }
  70.         return lps;
  71.     }
  72. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
spoj: The program compiled successfully, but main class was not found.
      Main class should contain method: public static void main (String[] args).
stdout
copy 
Standard output is empty
https://ideone.com/Rhg37V
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!