Cod sursa(job #1445705)

Utilizator LASM_CodersLASM Chihai Motroi LASM_Coders Data 30 mai 2015 20:41:15
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<string>
#include<vector>

#define min(a,b) a<b ? a : b

using namespace std;

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

string pattern, text, s;
int n,L;
int z[1<<21];
vector<int> v;

int main() {
    
    cin>>pattern>>text;
    s=pattern+'*'+text;
    
    n=s.size();
    for (int i=1,l=0,r=-1;i<n;i++)
    {
     if (i<=r) z[i]=min(z[i-l],r-i+1);
     while  ( i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++;
     if (i+z[i]-1>r) l=i, r=i+z[i]-1;
    }
    
    for (int i=0;i<text.size();i++)
     if (z[pattern.size()+1+i]==pattern.size())
      v.push_back(i);
      
     L=min(1000,v.size());
     cout<<v.size()<<endl;
     for (int i=0;i<L;i++)
      cout<<v[i]<<' ';
      
     
     return 0; }