Pagini recente » Cod sursa (job #1353694) | Cod sursa (job #3214829) | Cod sursa (job #1422174) | Cod sursa (job #2689416) | Cod sursa (job #2321565)
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
char pattern[Nmax], sir[Nmax];
int i, j, n, m, suf[Nmax], v[1005], k;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(pattern, sizeof(pattern));
f.getline(sir, sizeof(sir));
i = 1;
j = 0;
n = strlen(pattern);
m = strlen(sir);
while(i < n)
{
while(j > 0 && pattern[i] != pattern[j])j = pattern[j - 1];
if(pattern[i] == pattern[j])
{
suf[i] = j + 1;
i++;
j++;
}
else i ++;
}
i = 0;
j = 0;
while(i < m)
{
while(j > 0 && sir[i] != pattern[j])j = suf[j - 1];
if(sir[i] == pattern[j])
{
i++;
j++;
if(j == n)v[++k] = i - n;
}
else i++;
}
g << k << "\n";
for(i = 1; i <= k; i ++)
g << v[i] << " ";
return 0;
}