KMP

string a, b;
cin >> a >> b;
string s = b;
s += '#'; s += a;
lps[0] = 0;
for (int i = 1; i < s.length(); i++) {
    int len = lps[i - 1];
    while (len > 0 && s[len] != s[i])
         len = lps[len - 1];
    if (s[i] == s[len])
         len++;
    lps[i] = len;
    if (lps[i] == b.size())
        v.pb(i);
}