Cod sursa(job #790312)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 20 septembrie 2012 20:53:50
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

char p[2000000],t[2000000];
int urm[2000000];
vector<int> v;
int n,m;



void next(char* p)
{
    int k=-1;
    urm[0]=0;
    for(int x=1;x<m;x++)
    {
        while( k>0 && p[k+1]!=p[x] )
        {
            k=urm[k];
        }
        if(p[k+1]==p[x])
            k++;
        urm[x] = k;
        if(urm[x]==-1)
            urm[x] = 0;
    }
}

int main()
{
    int x=-1;
    fin.getline(p,2000000);
    fin.getline(t,2000000);
    n=strlen(t);
    m=strlen(p);
    next(p);
    for(int i=0;i<n;i++)
    {
        while(x>0 && p[x+1]!=t[i])
            x=urm[x];
        if(p[x+1]==t[i])
            x++;
        if(x==m-1)
        {
            v.push_back(i-m+1);
            x=urm[x];
        }
    }
    fout<<v.size()<<'\n';
    for(unsigned int i=0;i<v.size();i++)
        fout<<v[i]<<' ';
    fin.close();
    fout.close();
    return 0;
}