fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class Ideone {
  8. 	int[] f;
  9. 	public void dfa(String pattern) {
  10. 		int m = pattern.length();
  11. 		f = new int[m+1];
  12. 		f[0] = 0;
  13. 		f[1] = 0;
  14. 		for(int i=2; i<=m; i++) {
  15. 			int j = f[i-1];
  16. 			for(;;) {
  17. 				if(pattern.charAt(j) == pattern.charAt(i-1)) {
  18. 					f[i] = j +1;
  19. 					break;
  20. 				}
  21. 				if(j==0) {
  22. 					f[i] = 0;
  23. 					break;
  24. 				}
  25. 				j = f[j];
  26. 			}
  27. 		}
  28. 	}
  29.  
  30. 	public int match(String text, String pattern) {
  31. 		dfa(pattern);
  32. 		int n = text.length();
  33. 		int m = pattern.length();
  34. 		int i = 0;
  35. 		int j = 0;
  36. 		for(;;) {
  37. 			if(i == n) break;
  38. 			if(text.charAt(i) == pattern.charAt(j)) {
  39. 				j++;
  40. 				i++;
  41. 				if(j == m) return i;
  42. 			}
  43. 			else if(j > 0) j =f[j];
  44. 			else i++;
  45. 		}
  46. 		return -1;
  47. 	}
  48.  
  49. 	public static void main(String[] args) {
  50. 		Ideone kmp = new Ideone();
  51. 		String text = "AĄĘĆABA";
  52. 		String pattern = "ĄĘĆ";
  53. 		System.out.println(kmp.match(text, pattern));
  54. 	}
  55. }
  56.  
Success #stdin #stdout 0.09s 27704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/y8NknW
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

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!