Pagini recente » Cod sursa (job #2293133) | Cod sursa (job #1633473) | Cod sursa (job #2901602) | Cod sursa (job #2975487) | Cod sursa (job #2433550)
#include <cstring>
#include <fstream>
#define maxn 2000005
using namespace std;
int rasp[maxn], nr;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
void computeLPSArray(char* pat, int M, int* lps);
void rez1(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while(i < N)
{
if(pat[j] == txt[i])
{
i++;
j++;
}
else
{
if(j == M)
rasp[++nr] = i - j, j = lps[j - 1];
else if( i < N && pat[j] != txt[i])
if(j)
j = lps[j - 1];
else
i++;
}
}
}
void computeLPSArray(char* pat, int M, int* lps)
{
int i = 1;
int lens = 0;
lps[0] = 0;
while(i < M)
{
if(pat[lens] == pat[i])
{
lens++;
lps[i] = lens;
i++;
}
else
{
if(lens > 0)
lens = lps[lens-1];
else
{
lps[i] = 0;
i++;
}
}
}
}
char pat[maxn], txt[maxn];
int main()
{
cin >> pat >> txt;
rez1(pat, txt);
cout << nr << '\n';
for(int i = 1; i <= nr; i++)
cout << rasp[i] << ' ';
return 0;
}