Cod sursa(job #2954888)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 15 decembrie 2022 18:54:52
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#define _CRT_SECURE_NO_WARNINGS
#include <math.h>
#include <vector>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <bitset>
#include <string>
//#include <bits/stdc++.h>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

const int mod = 1e9 + 7;
const int NMAX = 20;
const double eps = 1e-7;                                                     

char str[200];

int n, m;

void read()
{
    cin >> str;
    n = strlen(str);
    str[n] = '#';
    cin >> (str + n + 1);
    m = strlen(str);
}

int pref[2003], len;
int nr1;
vector<int> p;
void solution()
{
    for (int i = 1; i < m; ++i)
    {
        len = pref[i - 1];
        while (len > 0 && str[i] != str[len])
            len = pref[len - 1];
        if (str[i] == str[len])
            len++;
        pref[i] = len;
        if (len == n && nr1<=1000)
            p.push_back(i-n-n), nr1++;
    }
    int nr = 0;
    cout << p.size() << '\n';
    while (p.size() - nr > 0)
        cout << p.front() << ' ', nr++;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    read();
    solution();
}