Cod sursa(job #2938617)

Utilizator alebbAlexandra Bochis alebb Data 12 noiembrie 2022 13:36:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

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

string s1,s2;
unsigned long long h1, h2, p_n=1;
long long p=31;
vector <int> prez;

int main()
{

    /*r=strstr(s2, s1);
    if(r)
        v[++nr]=r-s2;
    v[0]=0;
    while(r){
        strcpy(aux, r+1);
        r=strstr(aux, s1);
        if(r)
            nr++, v[nr]=r-aux+v[nr-1]+1;
    }
    cout<<nr<<'\n';
    for(int i=1; i<=nr; i++)
        cout<<v[i]<<' ';*/


    ///


    /*for(int i=1; i<strlen(s2)-strlen(s1); i++){
        bool ok=true;
        for(int j=0; j<strlen(s1) and ok; j++)
            if(s1[j]!=s2[i+j]) ok=false;
        if(ok) v[++nr]=i;

    }
    cout<<nr<<'\n';
    for(int i=1; i<=nr; i++)
        cout<<v[i]<<' ';*/

    ///

    fin>>s1>>s2;
    if(s1.size()> s2.size()) swap(s1, s2);

    for(int i=0; i<s1.size(); i++){
        h1=h1*p+s1[i];
        h2=h2*p+s2[i];
        p_n=p_n*p;
    }
    if(h1==h2)
        prez.push_back(0);
    for(int i=s1.size(); i<s2.size(); i++){
        h2=h2*p+s2[i]-p_n*s2[i-s1.size()];
        if(h1==h2)
            prez.push_back(i-s1.size()+1);
    }
    fout<<prez.size()<<'\n';
    for(int i=0; i<min(1000, (int)prez.size()); i++)
        fout<<prez[i]<<' ';
    return 0;
}