Cod sursa(job #2954896)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 15 decembrie 2022 19:09:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 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[4000002];

int pref[4000002], len;

int nr1;

int n, m;

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

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++;
            if (nr1 <= 1000)
                p.push_back(i - 2 * n);
        }
    }
    cout << nr1 << '\n';
    for (int i = 0; i < p.size(); ++i) {
        cout << p[i] << ' ';
    }
}

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