import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { String s = cin.next(); String t = cin.next(); kmp(s, t); } } public static int kmp(String s, String t) { int next[] = new int[t.length()]; getNext(t, next); int n = kmpMatch(s,t,next); System.out.println(n); return n; } private static int kmpMatch(String s, String t, int[] next) { int j=0; int len = t.length(); for(int i=0;i<s.length();i++) { if(s.charAt(i) == t.charAt(j) ) { if(j == len -1) return (i-len+2); j++; } else { while(next[j] != -1) { if(s.charAt(i) == t.charAt(next[j])) { j= next[j] +1; break; } else j= next[j]; } } } return 0; } private static void getNext(String t, int next[]) { next[0] = -1; for (int i = 1; i < t.length(); i++) { int k = next[i - 1]; if ( k!= -1 && t.charAt(k) == t.charAt(i-1)) next[i] = next[i - 1] + 1; else next[i] = 0; } } } /************************************************************** Problem: 2152 User: admin Language: Java Result: Accepted Time:674 ms Memory:39800 kb ****************************************************************/