Pagini recente » Cod sursa (job #406837) | Cod sursa (job #1990858) | Cod sursa (job #339639) | Cod sursa (job #416465) | Cod sursa (job #3329430)
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000000], B[2000000];
f>>A>>B;
int lenA=strlen(A);
vector<int> p(lenA);
int l=0;
for(int i=1; i<lenA; i++)
{
if(A[i]==A[l])
{
l++;
p[i]=l;
}
else
{
while(A[i]!=A[l] && l>0)
{
l=p[l-1];
}
if(A[i]==A[l])
{
l++;
}
p[i]=l;
}
}
int num=0;
l=0;
vector<int> poz;
int lenB=strlen(B);
for(int i=0; i<lenB; i++)
{
while(A[l]!=B[i] && l>0)
{
l=p[l-1];
}
if(A[l]==B[i])
{
l++;
}
if(lenA==l)
{
num++;
if(poz.size()<1000)
{
poz.push_back(i-lenA+1);
}
l=p[l-1];
}
}
g<<num<<endl;
for(int i=0; i<poz.size(); i++)
{
g<<poz[i]<<" ";
}
return 0;
}