Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.Scanner;
- public class Cwk1Problem6 {
- /**
- * @param args the command line arguments
- */
- public static void main(String[] args) throws FileNotFoundException {
- //Set up scanner.
- String filename = "Input.txt";
- Scanner input = new Scanner(new File(filename));
- //Get the text and pattern as strings.
- String text = input.nextLine();
- String pattern = input.nextLine();
- //Close the input file.
- input.close();
- //Find the next highest power of 2 above the current length.
- double power = Math.ceil(Math.log(text.length())/Math.log(2));
- double length = Math.pow(2, power);
- Complex[] t = new Complex[(int)length];
- Complex[] tSquared = new Complex[(int) length];
- Complex[] tCubed = new Complex[(int) length];
- Complex[] p = new Complex[(int) length];
- Complex[] pSquared = new Complex[(int) length];
- Complex[] pCubed = new Complex[(int)length];
- for (int i = 0; i<pattern.length(); i++)
- {
- //Inverse fills t, tSquared and tCubed.
- if (text.charAt(text.length()-i-1) == 63)
- {
- t[i]=new Complex(0,0);
- }
- else t[i] = new Complex(text.charAt(text.length()-i-1),0);
- tSquared[i] = new Complex(Math.pow(t[i].returnReal(),2) ,0);
- tCubed[i] = new Complex(Math.pow(t[i].returnReal(),3) ,0);
- //fills p, pSquared and PCubed
- if (pattern.charAt(i) == 63)
- {
- p[i]=new Complex(0,0);
- }
- else p[i] = new Complex(pattern.charAt(i),0);
- pSquared[i]=new Complex(Math.pow(p[i].returnReal(),2),0);
- pCubed[i]=new Complex(Math.pow(p[i].returnReal(),3),0);
- }
- for (int i=pattern.length(); i<text.length(); i++)
- {
- // Inverse fills t, tSquared and tCubed.
- if (text.charAt(text.length()-i-1) == 63)
- {
- t[i]=new Complex(0,0);
- }
- else {t[i] = new Complex(text.charAt(text.length()-i-1),0);}
- tSquared[i] = new Complex(Math.pow(t[i].returnReal(),2) ,0);
- tCubed[i] = new Complex(Math.pow(t[i].returnReal(),3) ,0);
- //Sets all p's as (0,0) as padding.
- p[i] = new Complex(0,0);
- pSquared[i] = new Complex(0,0);
- pCubed[i] = new Complex(0,0);
- }
- //Sets everything as (0,0) as padding.
- for (int i = text.length(); i<length; i++)
- {
- t[i] = new Complex(0,0);
- tSquared[i] = new Complex(0,0);
- tCubed[i] = new Complex(0,0);
- p[i] = new Complex(0,0);
- pSquared[i] = new Complex(0,0);
- pCubed[i] = new Complex(0,0);
- }
- Complex[] firstFourierOutput = FFT.multiplyPoly(pCubed,t,t.length);
- Complex[] secondFourierOutput = FFT.multiplyPoly(pSquared, tSquared, t.length);
- Complex[] thirdFourierOutput = FFT.multiplyPoly(p, tCubed, t.length);
- int[] firstSum = new int[text.length()-pattern.length()+1];
- int[] secondSum = new int[text.length() - pattern.length()+1];
- int[] thirdSum = new int [text.length()-pattern.length()+1];
- boolean result = false;
- for (int i=0; i<=text.length()-pattern.length(); i++)
- {
- firstSum[i] = (int)firstFourierOutput[text.length()-i-1].returnReal();
- secondSum[i] = (int)secondFourierOutput[text.length()-i-1].returnReal();
- thirdSum[i] = (int)thirdFourierOutput[text.length()-i-1].returnReal();
- if(firstSum[i]-2*secondSum[i]+thirdSum[i] == 0)
- {
- System.out.print(i);
- result = true;
- break;
- }
- }
- if (result == false) System.out.print("-1");
- }
- }
Add Comment
Please, Sign In to add comment