Cod sursa(job #3195113)

Utilizator lucatanasegLuca-Tanase Grindean lucatanaseg Data 20 ianuarie 2024 09:45:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000005], b[2000005];
int tabel[2000005];
int poz[1001];
int n,m;
int i,j,k;
int ans;
vector <int> res;

int main()
{
    fin>>a>>b;
    n=strlen(a); m=strlen(b);
    i=1;
    while(i<n){
        if(a[i]==a[k]){
            k++;
            tabel[i]=k;
            i++;
        }
        else  if(k!=0){
            k=tabel[k-1];
        }
        else{
            tabel[i]=0;
            i++;
        }
    }
    i=0;
    k=0;
    while(i<m){
        if(b[i]==a[k]){
            k++;
            i++;
            if(k==n){
                ans++;
                if(ans<=1000){
                    res.push_back(i-n);
                }
                k=tabel[k-1];
            }
        }
        else if(b[i]!=a[k]){
            if(k!=0){
                k=tabel[k-1];
            }
            else i++;
        }
    }
    fout<<ans<<'\n';
    for(auto x : res){
        fout<<x<<' ';
    }

    return 0;
}