Binary Key

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

bool d[2050][250];
bool pr[2050][250];

int main()
{
    string p, s;
    getline(cin, p);
    getline(cin, s);
    int k;
    cin >> k;
    string result = "";
    for (int cnt = 1; cnt <= min(k, (int)s.length()); ++cnt)
    {
        if (p.length() / k * cnt > s.length())
            break;
        d[k][cnt] = true;
        for (int j = 0; j < cnt; ++j)
            d[k][j] = false;
        for (int i = k - 1; i >= 0; --i)
        {
            d[i][cnt] = true;
            pr[i][cnt] = false;
            for (int j = cnt - 1; j >= 0; --j)
            {
                d[i][j] = false;
                if (d[i + 1][j])
                {
                    d[i][j] = true;
                    pr[i][j] = false;
                }
                else
                    if (d[i + 1][j + 1])
                    {
                        bool yes = true;
                        for (int cur1 = j, cur2 = i; cur1 < s.length() || cur2 < p.length(); cur1 += cnt, cur2 += k)
                            if (cur1 >= s.length() || cur2 >= p.length() || s[cur1] != p[cur2])
                            {
                                yes = false;
                                break;
                            }
                        if (yes)
                        {
                            d[i][j] = true;
                            pr[i][j] = true;
                        }
                    }
            }
        }
        if (!d[0][0])
            continue;
        string ans;
        int j = 0;
        for (int i = 0; i < k; ++i)
            if (pr[i][j])
            {
                ans += '1';
                ++j;
            }
            else
                ans += '0';
        if (result == "" || ans < result)
        result = ans;
    }
    if (result == "")
        cout << 0 << endl;
    else
        cout << result << endl;
    return 0;
}