fork(2) download
copy 
  1. import java.util.Scanner;
  2.  
  3.  
  4. class KMPAlgorithm {
  5.  
  6.  
  7. 	public static int[] setupKMP(String pattern)
  8. 	{
  9. 		int a[] = new int[pattern.length()];
  10. 		a[0]=0;
  11. 		int j=1;
  12. 		for(int i=2;i<pattern.length();)
  13. 		{
  14. 			if(pattern.charAt(j)==pattern.charAt(i))
  15. 			{
  16. 				j++;
  17. 				a[i]=j;
  18. 				i++;
  19. 			}
  20. 			else if(j>0)
  21. 			{
  22. 				j = a[j];
  23. 			}
  24. 			else
  25. 			{
  26. 				a[i]=0;
  27. 				i++;
  28. 			}
  29. 		}
  30. 		return a;
  31. 	}
  32. 	/**
  33. 	 * @param args
  34. 	 */
  35. 	public static void main(String[] args) {
  36. 		// TODO Auto-generated method stub
  37. 		Scanner in = new Scanner(System.in);
  38. 		String text = in.nextLine();
  39. 		String pattern = in.nextLine();
  40. 		int a[] = setupKMP(pattern);
  41. 		int j=0;
  42. 		for(int i=0;i<text.length();)
  43. 		{
  44. 			if(pattern.charAt(j)==text.charAt(i))
  45. 			{
  46. 				j++;
  47. 				i++;
  48. 			}
  49. 			else
  50. 			{
  51. 				if(j>0)
  52. 				{
  53. 					j = a[j-1];
  54. 				}
  55. 				else
  56. 				{
  57. 					i++;
  58. 				}
  59. 			}
  60. 			if(j==pattern.length())
  61. 			{
  62. 				System.out.println("pattern found at " + (i-pattern.length()+1));
  63. 			}
  64. 		}
  65. 	}
  66.  
  67. }
  68.  
Success #stdin #stdout 0.13s 321088KB
comments (?)
stdin
copy 
abababcd
ababcd
stdout
copy 
pattern found at 3
https://ideone.com/hcT47E
language:
Java (HotSpot 12)
created:
8 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!