Cod sursa(job #1322249)

Utilizator deea101Andreea deea101 Data 19 ianuarie 2015 21:44:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

vector < pair<int,int> > sol;
int countSol=0;

void prefix(string A, vector <int> &fail)
{
    int node=0;
    fail[0]=fail[1]=0;
    
    int m=A.size()-1;
    for(int i=2;i<=m;i++)
    {
        while(A[node+1]!=A[i] && node!=0)
            node=fail[node];

        if(A[node+1]==A[i])
            node++;

        fail[i]=node;
    }
}
        
vector <pair <int,int> > KMP (string A, string B)
{
    vector <int> fail (A.size(),0);
    prefix(A,fail);

    int node=0,m=A.size()-1,n=B.size()-1;
    for(int i=1;i<=n;i++)
    {
        while(A[node+1]!=B[i] && node!=0)
            node=fail[node];
        
        if(A[node+1]==B[i])
            node++;
        
        if(node==m)
		{
			countSol++;
			node=fail[node];
            if(countSol<=1000) sol.push_back(make_pair(i-m+1,i));
		}
    }
	return sol;
}

#include <iostream>
int main()
{
    string A,B;
    f>>A;
    f>>B;
	
	A.insert(A.begin(),'x');
	B.insert(B.begin(),'x');
   
    sol=KMP(A,B);
    g<<countSol<<'\n';
    for(int i=0;i<sol.size();i++)
        g<<sol[i].first-1<<' ';
}