Cod sursa(job #1253774)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 1 noiembrie 2014 19:41:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,m;
int pi[2000001];
string a,b;

void makepie();

int main()
{
    f>>a>>b;

    n = a.size();
    m = b.size();
    a.insert(a.begin(),1,' ');
    b.insert(b.begin(),1,' ');
    vector<int> sl;
    int nr=0;
    makepie();
    for(int i = 1, q = 0; i <= m; i++){
        while(q && a[q+1] != b[i])
            q = pi[q];
        if(a[q+1] == b[i])
            q++;
        if(q == n){
            nr++;
            if(sl.size()<1000)
                sl.push_back(i - n);
        }
    }
    g<<nr<<'\n';
    for(size_t i = 0;i < sl.size(); i++)
        g<<sl[i]<<" ";

    return 0;
}
void makepie()
{
    int q = 0;

    for(int i = 2; i<=n ; i++){
        while(q && a[q+1] != a[i])
            q = pi[q];
        if(a[q+1] == a[i])
            q++;
        pi[i] = q;
    }
}