Pagini recente » Cod sursa (job #437927) | Cod sursa (job #1225626) | Cod sursa (job #2160122) | Cod sursa (job #2693494) | Cod sursa (job #3329436)
/******************************************************************************
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;
char A[2000005], B[2000005];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>A>>B;
int lenA=strlen(A);
vector<int> p(lenA);
p[0]=0;
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(auto x : poz)
{
g<<x<<" ";
}
return 0;
}