Cod sursa(job #2945014)

Utilizator NashikAndrei Feodorov Nashik Data 23 noiembrie 2022 12:23:52
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int z[4000005];
int main() {
    string s,s2;
    cin>>s;
    int m=s.length();
    cin>>s2;
    s+='$';
    s+=s2;
    int n=s.length(),r=0,l=0;
    for(int i=1;i<n;i++) {
        if (i <= r) {
            z[i] = min(z[i - l], i - r + 1);
        }
        while (i + z[i] < n and s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(z[i]==m){
            cnt++;
        }
    }
    cout<<cnt<<"\n";
    if(cnt>1000)
        cnt=1000;
    for(int i=0;i<n and cnt!=0;i++){
        if(m==z[i]) {
            cnt--;
            cout << i - m - 1 << " ";
        }
    }
    return 0;
}