Cod sursa(job #3325468)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 25 noiembrie 2025 15:17:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <cstring>
#define nmax (int)(2e6+1)
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int n,m,lps[nmax],sol;
string s,a;
vector<int>poz;
void precalculare(){
    /// lps = longest prefix suffix
    int i=1,len=0;
    lps[0]=0;
    while(i<n){
        if(s[i]==s[len]){
            len++;
            lps[i++]=len;
        }else if(len==0)
            i++;
        else
            len=lps[len-1];
    }
}
int main()
{
    cin>>s>>a;
    n=s.size(),m=a.size();
    precalculare();
    int i=0,j=0;
    while(i<m){
        if(a[i]==s[j]){
            i++;
            j++;
        }else if(j!=0)
            j=lps[j-1];
        else
            i++;/// daca j==0
        if(j==n){
            j=lps[j-1];
            sol++;
            poz.push_back(i-n);
        }
    }
    cout<<poz.size()<<'\n';
    for(int i=0;i<min(sol,1001);i++)
        cout<<poz[i]<<" ";
	return 0;
}