Cod sursa(job #3178348)

Utilizator strimbumarkMark Strimbu strimbumark Data 1 decembrie 2023 16:50:52
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream cout("strmatch.out");


vector <int> a;

int pi[2000000];

int main()
{
   string t,s,tot;
   fin>>t>>s;
   tot=t+"#"+s;
   
   int n;
   n =tot.length();
   
   for(int i=1;i<=n;i++)
   {
        int j = pi[i-1];
        while(tot[j] != tot[i] && j>0)
            j = pi[j-1];
        if(tot[i] == tot[j])
            j++;
        pi[i]=j;
        
        
        
        if(pi[i] == t.size() && i>t.size())
            a.push_back(i- 2*t.size());
   }
   fout<<a.size()<<"\n";
   for(int i=0;i<a.size();i++)
        fout<<a[i]<<" ";
   
}