Cod sursa(job #2644793)

Utilizator xCata02Catalin Brita xCata02 Data 25 august 2020 22:39:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 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
*/

int contor = 0;
int nuStiuSTL[1005];
char a[2000005], b[2000005];
int dp[2000005];
int n, m;

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

void cautare() {
    init();

    int j = 0;
    for(int i = 1; i <= n; i++) {
        while(j && a[j + 1] != b[i]) {
            j = dp[j];
        }
        if(a[j + 1] == b[i]) {
            j++;
        }
        if(j == m) {
            j = dp[m];
            contor++;
            if(contor <= 1000) {
                nuStiuSTL[contor] = i - m;
            }
        }
    }
}

void solve() {
    a[0] = '.';
    b[0] = '.';
   cin >> (a + 1) >> (b + 1);
   n = strlen(b) - 1;
   m = strlen(a) - 1;

   cautare();
   if(contor > 1000) {
    contor = 1000;
   }
   cout << contor << endl;
   for(int i = 1; i <= contor; i++) {
        cout << nuStiuSTL[i] << " ";
   }
}

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

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