Cod sursa(job #1445707)

Utilizator LASM_CodersLASM Chihai Motroi LASM_Coders Data 30 mai 2015 20:52:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 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 text, pattern , s;
int n, pi[1<<22], L;
vector<int> v;

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