#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000009, A = 131, invA = 526717562;
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int wlen = words[0].length(), slen = s.length(), wnum = words.size();
        vector<ll> apow(wlen, 1);
        for(int i = 1 ; i < wlen ; i++)
            apow[i] = (apow[i - 1] * A) % MOD;
        vector<ll> hwords(words.size()), hs(slen);
        ll key = 0;
        for(int i = 0 ; i < (int)words.size() ; i++){
            for(int j = 0 ; j < wlen ; j++){
                hwords[i] += apow[j] * words[i][j];
                hwords[i] %= MOD;
            }
            //printf("h[%d] = %lld\n", i, hwords[i]);
            key += hwords[i];
            key %= MOD;
        }
        //printf("key = %lld\n", key);
        for(int i = 0 ; i < wlen ; i++){
            hs[0] += apow[i] * s[i];
            hs[0] %= MOD;
        }
        //printf("s[0] = %lld\n", hs[0]);
        for(int i = 1 ; i <= slen - wlen ; i++){
            hs[i] = (hs[i - 1] - s[i - 1]) * invA + apow[wlen - 1] * s[i + wlen - 1];
            hs[i] = (hs[i] % MOD + MOD) % MOD;
            //printf("s[%d] = %lld\n", i, hs[i]);
        }
        vector<int> ans;
        for(int i = 0 ; i < wlen ; i++){
            int j = i;
            ll nkey = 0;
            while(j < wnum * wlen)
                nkey += hs[j], nkey %= MOD, j += wlen;
            while(j < slen){
                //printf("%d %lld\n", j, nkey);
                if(nkey == key)
                    ans.push_back(j - wnum * wlen);
                nkey += hs[j] - hs[j - wnum * wlen];
                nkey = (nkey % MOD + MOD) % MOD;
                j += wlen;
            }
            if(nkey == key)
                ans.push_back(j - wnum * wlen);
        }
        return ans;
    }
};

int main(){
    Solution sol;
    string s = "barfoothefoobarman";
    vector<string> words = {"bar", "foo"};
    s = "wordgoodgoodgoodbestword";
    words = {"word","good","best","good"};
    auto ans = sol.findSubstring(s, words);
    for(int x : ans)
        printf("%d\n", x);
    return 0;
}