Cod sursa(job #2173779)

Utilizator NicuBaciuNicu Baciu NicuBaciu Data 16 martie 2018 00:51:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

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

string pattern;
string text;

int nrmatch=0;
vector <int> res;

int pref[2000002];

void gen_pref(string s)
{
    int j=0;

    for(int i=1; i<s.size(); i++)
    {
        if(s[i]==s[j])
        {
            pref[i]=j+1;
            j++;
        }
        else
        {
            while(j>0)
            {
                j=pref[j-1];
                if(s[j]==s[i])
                {
                    pref[i]=j+1;
                    j++;
                    break;
                }
            }

            if(j==0)
            {
                if(s[j]!=s[i])
                    pref[i]=0;
                else
                {
                    pref[i]=j+1;
                    j++;
                }
            }

        }
    }
}

void solve(string t, string p)
{
    int j=0;

    for(int i=0; i<t.size(); i++)
    {
        if(t[i]==p[j])
        {
            if(j==p.size()-1)
            {
                nrmatch++;

                if(nrmatch<=1000)
                {
                    res.push_back(i-p.size()+1);
                }

                j=pref[j];
            }
            else
                j++;
        }
        else if(j!=0)
        {
            j=pref[j-1];
            i--;
        }
    }
}

int main()
{
    getline(fin, pattern);
    getline(fin, text);

    gen_pref(pattern);

    solve(text, pattern);

    fout << nrmatch << '\n';

    for(int i=0; i<res.size(); i++)
        fout << res[i] << " ";

    return 0;
}