Cod sursa(job #2645853)

Utilizator xCata02Catalin Brita xCata02 Data 29 august 2020 19:15:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"

/*
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
#define cin  fin
#define cout fout
*/

ifstream fin("test.in");
#define cin fin

int n, m;
string a, b;
int dp[2000005];
vector < int > sol;

void init() {
    int j = 0;
    dp[1] = 0;
    for(int i = 2; i <= n; i++) {
        while(j && a[j + 1] != a[i]) {
            j = dp[j];
        }
        if(a[j + 1] == a[i]) {
            j++;
        }
        dp[i] = j;
    }
}

void fao() {
    int j = 0;
    for(int i = 1; i <= m; i++) {
        while(j && a[j + 1] != b[i]) {
            j = dp[j];
        }
        if(a[j + 1] == b[i]) {
            j++;
        }
        if(j == n) {
            j = dp[n];
            if(sol.size() <= 1000) {
                sol.push_back(i - n);
            }
        }
    }
}

void solve() {
    cin >> a >> b;
    n = a.size();
    m = b.size();

    a = '.' + a;
    b = '.' + b;

    init();
    fao();

    cout << sol.size() << endl;
    for(auto it : sol) {
        cout << it << " ";
    }
}

int main() {
	ios_base::sync_with_stdio(0);
	cin .tie(0);
	cout.tie(0);

	int testCases = 1;
	//cin >> testCases;
	while(testCases--) {
		solve();
	}
}