Guest User

Untitled

a guest
May 20th, 2018
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.96 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.Scanner;
  3. public class Cwk1Problem6 {
  4.  
  5.     /**
  6.      * @param args the command line arguments
  7.      */
  8.    
  9.     public static void main(String[] args) throws FileNotFoundException {
  10.                 //Set up scanner.
  11.         String filename = "Input.txt";
  12.         Scanner input = new Scanner(new File(filename));
  13.        
  14.         //Get the text and pattern as strings.
  15.         String text = input.nextLine();
  16.         String pattern = input.nextLine();
  17.        
  18.         //Close the input file.
  19.         input.close();
  20.         //Find the next highest power of 2 above the current length.
  21.         double power = Math.ceil(Math.log(text.length())/Math.log(2));
  22.         double length = Math.pow(2, power);
  23.        
  24.         Complex[] t = new Complex[(int)length];
  25.         Complex[] tSquared = new Complex[(int) length];
  26.         Complex[] tCubed = new Complex[(int) length];
  27.         Complex[] p = new Complex[(int) length];
  28.         Complex[] pSquared = new Complex[(int) length];
  29.         Complex[] pCubed = new Complex[(int)length];
  30.        
  31.         for (int i = 0; i<pattern.length(); i++)
  32.         {
  33.             //Inverse fills t, tSquared and tCubed.
  34.             if (text.charAt(text.length()-i-1) == 63)
  35.             {
  36.                 t[i]=new Complex(0,0);
  37.             }
  38.             else t[i] = new Complex(text.charAt(text.length()-i-1),0);
  39.            
  40.             tSquared[i]  = new Complex(Math.pow(t[i].returnReal(),2) ,0);
  41.             tCubed[i] = new Complex(Math.pow(t[i].returnReal(),3) ,0);
  42.             //fills p, pSquared and PCubed
  43.             if (pattern.charAt(i) == 63)
  44.             {
  45.                 p[i]=new Complex(0,0);
  46.             }
  47.             else p[i] = new Complex(pattern.charAt(i),0);
  48.             pSquared[i]=new Complex(Math.pow(p[i].returnReal(),2),0);
  49.             pCubed[i]=new Complex(Math.pow(p[i].returnReal(),3),0);
  50.         }
  51.         for (int i=pattern.length(); i<text.length(); i++)
  52.         {
  53.            // Inverse fills t, tSquared and tCubed.
  54.            if (text.charAt(text.length()-i-1) == 63)
  55.             {
  56.                 t[i]=new Complex(0,0);
  57.             }
  58.             else {t[i] = new Complex(text.charAt(text.length()-i-1),0);}
  59.            tSquared[i]  = new Complex(Math.pow(t[i].returnReal(),2) ,0);
  60.            tCubed[i] = new Complex(Math.pow(t[i].returnReal(),3) ,0);
  61.            //Sets all p's as (0,0) as padding.
  62.            p[i] = new Complex(0,0);
  63.            pSquared[i] = new Complex(0,0);
  64.            pCubed[i] = new Complex(0,0);
  65.         }
  66.         //Sets everything as (0,0) as padding.
  67.         for (int i = text.length(); i<length; i++)
  68.         {
  69.             t[i] = new Complex(0,0);
  70.             tSquared[i] = new Complex(0,0);
  71.             tCubed[i] = new Complex(0,0);
  72.             p[i] = new Complex(0,0);
  73.             pSquared[i] = new Complex(0,0);
  74.             pCubed[i] = new Complex(0,0);
  75.         }
  76.        
  77.         Complex[] firstFourierOutput = FFT.multiplyPoly(pCubed,t,t.length);
  78.         Complex[] secondFourierOutput = FFT.multiplyPoly(pSquared, tSquared, t.length);
  79.         Complex[] thirdFourierOutput = FFT.multiplyPoly(p, tCubed, t.length);
  80.         int[] firstSum = new int[text.length()-pattern.length()+1];
  81.         int[] secondSum = new int[text.length() - pattern.length()+1];
  82.         int[] thirdSum = new int [text.length()-pattern.length()+1];
  83.         boolean result = false;
  84.         for (int i=0; i<=text.length()-pattern.length(); i++)
  85.         {
  86.             firstSum[i] = (int)firstFourierOutput[text.length()-i-1].returnReal();
  87.             secondSum[i] = (int)secondFourierOutput[text.length()-i-1].returnReal();
  88.             thirdSum[i] = (int)thirdFourierOutput[text.length()-i-1].returnReal();
  89.            
  90.             if(firstSum[i]-2*secondSum[i]+thirdSum[i] == 0)
  91.             {
  92.                 System.out.print(i);
  93.                 result = true;
  94.                 break;
  95.             }
  96.         }
  97.         if (result == false) System.out.print("-1");
  98.     }
  99. }
Add Comment
Please, Sign In to add comment