Cod sursa(job #3195731)

Utilizator abelesefBurduhos Abel abelesef Data 21 ianuarie 2024 16:07:49
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005],b[2000005];
int table[2000005];
vector < int > res; // primii 1000 de indici ca solutii
int ans;
int n,m;
int i,k;
int main() {
        fin>>a>>b;
        n = strlen(a);
        m = strlen(b);
        table[0] = 0;
        k = 0;
        i = 1;
        while(i<n) {
                if (a[i] == a[k]) {
                        k++;
                        table[i] = k;
                        i++;
                } else if (k!=0) {
                        k = table[k-1];
                } else {
                        table[i] = 0;
                        i++;
                }
        }
        i = 0,k = 0;
        while(i<m) {
                if (b[i] == a[k]) {
                        i++;
                        k++;
                        if (k==n) {
                                ans++;
                                if (ans<=1000) res.push_back(i-n);
                                k = table[k-1];
                        }
                } else if (b[i] != a[k]) {
                        if (k!=0)
                                k = table[k-1];
                        else
                                i++;
                }
        }
        fout<<ans<<endl;
        for (auto el : res) {
                fout<<el<<" ";
        }
        return 0;
}