Cod sursa(job #2644669)

Utilizator xCata02Catalin Brita xCata02 Data 25 august 2020 15:17:56
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
#include <sstream>
using namespace std;

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

const int Nmax = 1500;


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


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

vector < int > sol;

void init(string a, vector < int > &dp) {
    int j = 0;
    dp[0] = -1;
    int i = 1;
    while(i < a.size()) {
        if(a[i] == a[j]) {
            j++;
            dp[i] = j;
            i++;
        } else {
            if(j != 0) {
                j = dp[j - 1];
            } else {
                dp[i] = 0;
                i++;
            }
        }
    }
}

void cauta(string a, string b) {
    int m = a.size();
    int n = b.size();

    vector < int > dp(m, 0);
    init(a, dp);

    int i = 0;
    int j = 0;
    while(i < n) {
        if(a[j] == b[i]) {
            i++;
            j++;
        }

        if(j == m) {
            sol.push_back(i - j);
            if(sol.size() > 1000) {
                return;
            }
            j = dp[j - 1];
        } else if(i < n && a[j] != b[i]) {
            if(j != 0) {
                j = dp[j - 1];
            } else {
                i++;
            }
        }
    }
}

void solve() {
    string a, b;
    cin >> a >> b;
    cauta(a, b);
    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();
	}
}