Cod sursa(job #1724596)

Utilizator MithrilBratu Andrei Mithril Data 3 iulie 2016 16:28:36
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");ofstream fout("strmatch.out");
string text,pattern;
vector <int> where;
int aparitii = 0;


vector <int> make_temp( string s )
{
    vector <int> temp(s.size());
    int j=0;
    for(int i=1 ; i<s.size() ;)
    {
        if(s[i]==s[j]){temp[i]=j+1;i++;j++;}
        else
        {
            if( j!=0 ) j=temp[j-1];
            else{temp[i]=0;i++;}
        }
    }
    return temp;
}

int main()
{
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    where.reserve(1000);
    fin>>pattern>>text;
    auto temp = make_temp( pattern );
    if(pattern.size() > text.size()) fout<<0;
    else
    {
        int i=0,j=0;
        while( i<text.size() )
        {
            if(text[i]==pattern[j]){i++;j++;}
            else
            {
                if( j != 0)
                    j=temp[j-1];
                else
                    i++;
            }
            if( j == pattern.size() )
            {
                aparitii++;
                i--;
                if(aparitii<=1000)where.push_back(i-pattern.size()+1);
                j=temp[j];

            }
        }
    }
    fout<<aparitii<<'\n';
    for(auto i:where) fout<<i<< ' ';
    return 0;
}